Count Inversions in Array in DSA Typescript

Mental Model

Count how many pairs of numbers are out of order in an array. Each pair where a bigger number comes before a smaller one is an inversion.

Analogy: Imagine a line of people waiting by height. Every time a taller person stands before a shorter one, it's like an inversion. Counting all these pairs tells us how mixed up the line is.

Array: [2, 4, 1, 3, 5]
Inversions: (2,1), (4,1), (4,3)
Visual:
2 -> 4 -> 1 -> 3 -> 5
 ↑    ↑    ↑
Pairs out of order

Dry Run Walkthrough

Input: array: [2, 4, 1, 3, 5]

Goal: Count all pairs where a bigger number appears before a smaller number

Step 1: Split array into two halves: left=[2,4], right=[1,3,5]

Left: 2 -> 4
Right: 1 -> 3 -> 5

Why: Divide to conquer smaller parts for easier counting

Step 2: Split left half again: left_left=[2], left_right=[4]

Left_Left: 2
Left_Right: 4

Why: Keep dividing until subarrays have one or two elements

Step 3: Count inversions in left_left: single element 2, zero inversions

2 (sorted)

Why: Single element means zero inversions

Step 4: Count inversions in left_right: single element 4, zero inversions

4 (sorted)

Why: Single element means zero inversions

Step 5: Merge left_left and left_right: merge [2] and [4], count inversions

2 <= 4, no inversion
Merged: 2 -> 4

Why: Two elements in order means zero inversions

Step 6: Split right half: right_left=[1], right_right=[3,5]

Right_Left: 1
Right_Right: 3 -> 5

Why: Divide right half further

Step 7: Count inversions in right_left: single element 1, zero inversions

1 (sorted)

Why: Single element means zero inversions

Step 8: Count inversions in right_right: compare 3 and 5, no inversion

3 -> 5 (sorted)

Why: Two elements in order means zero inversions

Step 9: Merge right_left and right_right: merge [1] and [3,5], count inversions

1 <= 3, no inversion
Merged: 1 -> 3 -> 5

Why: No smaller element in right half before bigger in left half

Step 10: Merge sorted left half [2,4] with sorted right half [1,3,5], count inversions

1 < 2, inversion pairs: (2,1), (4,1)
3 < 4, inversion pair: (4,3)
Merged: 1 -> 2 -> 3 -> 4 -> 5

Why: Count cross inversions between halves during merge

Result:

1 -> 2 -> 3 -> 4 -> 5
Total inversions: 3

Annotated Code

DSA Typescript

class CountInversions {
  static mergeSort(arr: number[]): [number[], number] {
    if (arr.length <= 1) return [arr, 0];

    const mid = Math.floor(arr.length / 2);
    const [left, leftInv] = this.mergeSort(arr.slice(0, mid));
    const [right, rightInv] = this.mergeSort(arr.slice(mid));

    const [merged, mergeInv] = this.merge(left, right);
    return [merged, leftInv + rightInv + mergeInv];
  }

  private static merge(left: number[], right: number[]): [number[], number] {
    let i = 0, j = 0;
    const merged: number[] = [];
    let inversions = 0;

    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        merged.push(left[i]);
        i++;
      } else {
        merged.push(right[j]);
        inversions += left.length - i; // Count inversions
        j++;
      }
    }

    // Append remaining elements
    while (i < left.length) {
      merged.push(left[i]);
      i++;
    }
    while (j < right.length) {
      merged.push(right[j]);
      j++;
    }

    return [merged, inversions];
  }
}

// Driver code
const input = [2, 4, 1, 3, 5];
const [sorted, count] = CountInversions.mergeSort(input);
console.log(sorted.join(' -> ') + ' -> null');
console.log('Total inversions:', count);

if (arr.length <= 1) return [arr, 0];

Base case: single element or empty array has zero inversions

const mid = Math.floor(arr.length / 2);

Divide array into two halves

const [left, leftInv] = this.mergeSort(arr.slice(0, mid));

Recursively count inversions in left half

const [right, rightInv] = this.mergeSort(arr.slice(mid));

Recursively count inversions in right half

const [merged, mergeInv] = this.merge(left, right);

Merge two sorted halves and count cross inversions

if (left[i] <= right[j]) { merged.push(left[i]); i++; } else { merged.push(right[j]); inversions += left.length - i; j++; }

Count inversions when right element is smaller than left element

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Total inversions: 3

Complexity Analysis

Time: O(n log n) because the array is repeatedly split and merged, counting inversions during merges

Space: O(n) due to temporary arrays created during merge steps

vs Alternative: Naive approach is O(n^2) by checking all pairs; merge sort method is much faster for large arrays

Edge Cases

Empty array

Returns zero inversions immediately

DSA Typescript

if (arr.length <= 1) return [arr, 0];

Array with one element

Returns zero inversions immediately

DSA Typescript

if (arr.length <= 1) return [arr, 0];

Array with all elements equal

No inversions counted because no element is smaller after a bigger one

DSA Typescript

if (left[i] <= right[j]) { merged.push(left[i]); i++; }

When to Use This Pattern

When asked to count how many pairs are out of order in an array, use the merge sort inversion counting pattern because it efficiently counts cross pairs during merging.

Common Mistakes

Mistake: Counting inversions only within halves and forgetting cross inversions during merge
Fix: Add inversions count when merging by adding left.length - i when right[j] < left[i]

Mistake: Not returning the sorted array along with inversion count, causing incorrect merges
Fix: Return both merged array and inversion count from merge function

Summary

Counts how many pairs in an array are out of order using a modified merge sort.

Use it when you need to measure how unsorted an array is efficiently.

The key insight is counting inversions during the merge step by tracking how many elements remain in the left half when a smaller right element is placed.

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