Count Inversions in Array in DSA Typescript - Build from Scratch

Count Inversions in Array

📖 Scenario: Imagine you have a list of numbers representing the order of books on a shelf. You want to find out how many pairs of books are out of order compared to their correct sorted order. This count is called the number of inversions.

🎯 Goal: You will write a TypeScript program to count how many pairs of numbers in an array are inverted, meaning the first number is bigger than the second but appears before it in the list.

📋 What You'll Learn

Create an array called numbers with the exact values: [2, 4, 1, 3, 5]

Create a variable called inversionCount and set it to 0

Use a nested for loop with variables i and j to compare elements in numbers

Increase inversionCount by 1 each time you find numbers[i] > numbers[j] where i < j

Print the value of inversionCount

💡 Why This Matters

🌍 Real World

Counting inversions helps measure how far a list is from being sorted, useful in sorting algorithms and analyzing data order.

💼 Career

Understanding inversion counting is important for software engineers working on sorting, data analysis, and algorithm optimization.

1

Create the array of numbers

Create an array called numbers with these exact values: [2, 4, 1, 3, 5]

DSA Typescript

// Your code here

Hint

Use const numbers = [2, 4, 1, 3, 5]; to create the array.

2

Create the inversion count variable

Create a variable called inversionCount and set it to 0

DSA Typescript

const numbers = [2, 4, 1, 3, 5];
// Your code here

Hint

Use let inversionCount = 0; to start counting from zero.

3

Count the inversions using nested loops

Use a nested for loop with variables i and j to compare elements in numbers. Increase inversionCount by 1 each time you find numbers[i] > numbers[j] where i < j

DSA Typescript

const numbers = [2, 4, 1, 3, 5];
let inversionCount = 0;
// Your code here

Hint

Use two loops: outer loop with i from 0 to length, inner loop with j from i + 1 to length. Inside, check if numbers[i] > numbers[j] and increase inversionCount.

4

Print the inversion count

Print the value of inversionCount using console.log

DSA Typescript

const numbers = [2, 4, 1, 3, 5];
let inversionCount = 0;
for (let i = 0; i  numbers[j]) {
            inversionCount++;
        }
    }
}
// Your code here

Hint

Use console.log(inversionCount); to show the result.

Practice

1. What does the term inversion mean in the context of an array?

easy

A. The sum of all elements in the array

B. A pair of elements where the first is smaller than the second and appears before it

C. The total number of elements in the array

D. A pair of elements where the first is greater than the second and appears before it

Solution

1. Step 1: Understand the definition of inversion

   An inversion is a pair of elements (i, j) such that i < j but array[i] > array[j].

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it correctly describes this condition. Other options describe unrelated concepts.

3. Final Answer:

   A pair of elements where the first is greater than the second and appears before it -> Option D

4. Quick Check:

   Inversion = pair where earlier element > later element [OK]

Hint: Inversion means earlier bigger than later element [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts total elements
• Mixing up greater and smaller element order

2. Which of the following TypeScript function signatures correctly represents a function to count inversions in an array of numbers?

easy

A. function countInversions(arr: string): number[]

B. function countInversions(arr: number): string

C. function countInversions(arr: number[]): number

D. function countInversions(arr: any): void

Solution

1. Step 1: Analyze the function purpose and parameters

   The function should take an array of numbers and return a number representing the count of inversions.

2. Step 2: Match the correct signature

   function countInversions(arr: number[]): number matches this: input is number array, output is number. Others mismatch input/output types.

3. Final Answer:

   function countInversions(arr: number[]): number -> Option C

4. Quick Check:

   Input array, output number count [OK]

Hint: Input array of numbers, output single number [OK]

Common Mistakes:

• Using wrong input type like string instead of array
• Returning array instead of number
• Using void return type when output is needed

3. What is the output of the following TypeScript code?

function countInversions(arr: number[]): number {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) count++;
    }
  }
  return count;
}

console.log(countInversions([2, 4, 1, 3, 5]));

medium

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Identify all inversion pairs in the array

   Array: [2, 4, 1, 3, 5]. Inversions are (2,1), (4,1), (4,3). Total 3 inversions.

2. Step 2: Confirm the count returned by the nested loops

   The nested loops count each inversion correctly, so output is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Inversions = 3 [OK]

Hint: Count pairs where earlier > later element [OK]

Common Mistakes:

• Counting pairs incorrectly by missing some
• Confusing equal elements as inversions
• Off-by-one errors in loops

4. The following code attempts to count inversions but has a bug. What is the bug?

function countInversions(arr: number[]): number {
  let count = 0;
  for (let i = 0; i <= arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) count++;
    }
  }
  return count;
}

medium

A. The inner loop should start from j = 0 instead of i + 1

B. The outer loop condition should be < instead of <= to avoid out-of-bounds

C. The count variable should be reset inside the outer loop

D. The comparison should be arr[i] < arr[j] instead of >

Solution

1. Step 1: Analyze the outer loop condition

   The outer loop runs from i = 0 to i <= arr.length, which means i can be arr.length, causing arr[i] to be undefined (out-of-bounds).

2. Step 2: Correct the loop condition

   Changing to i < arr.length prevents out-of-bounds access and fixes the bug.

3. Final Answer:

   The outer loop condition should be < instead of <= to avoid out-of-bounds -> Option B

4. Quick Check:

   Loop bounds must prevent out-of-range access [OK]

Hint: Use < length, not <= length in loops [OK]

Common Mistakes:

• Using <= causes index out-of-bounds error
• Resetting count inside loop loses total count
• Changing comparison reverses inversion logic

5. Given the array [8, 4, 2, 1], which approach is the most efficient to count inversions and what is the inversion count?

hard

A. Use a modified merge sort to count inversions; count is 6

B. Use nested loops to count inversions; count is 3

C. Sort the array and count differences; count is 4

D. Use a hash map to count inversions; count is 5

Solution

1. Step 1: Identify inversion count manually

   Array: [8,4,2,1]. Inversions are (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) totaling 6.

2. Step 2: Choose the most efficient method

   Modified merge sort counts inversions in O(n log n), better than nested loops O(n²). Hash map or sorting differences do not directly count inversions.

3. Final Answer:

   Use a modified merge sort to count inversions; count is 6 -> Option A

4. Quick Check:

   Merge sort method = 6 inversions [OK]

Hint: Use merge sort for large arrays to count inversions fast [OK]

Common Mistakes:

• Counting inversions incorrectly by missing pairs
• Using nested loops for large arrays causing slow performance
• Confusing sorting with inversion counting