Count Inversions in Array in DSA Javascript

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
 ↑         ↑
 bigger before smaller pairs

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,1], right=[3,5]

left: 2 -> 4 -> 1
right: 3 -> 5

Why: Divide to conquer by counting inversions in smaller parts

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

left_left: 2 -> 4
left_right: 1

Why: Keep dividing until subarrays have one or two elements

Step 3: Count inversions in left_left by comparing 2 and 4: no inversion

2 -> 4 (sorted)

Why: Two elements sorted, no inversion here

Step 4: Merge left_left and left_right while counting inversions: compare 2 and 1, inversion found

Merged left: 1 -> 2 -> 4

Why: 1 is smaller than 2 and 4, so count inversions for these pairs

Step 5: Count inversions in right half: 3 and 5 are sorted, no inversion

3 -> 5

Why: Right half is already sorted

Step 6: Merge left and right halves while counting cross inversions: compare 4 and 3, inversion found

Final sorted array: 1 -> 2 -> 3 -> 4 -> 5

Why: 4 comes before 3 in original, so count this inversion

Result:

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

Annotated Code

DSA Javascript

class CountInversions {
  // Merge two sorted halves and count cross inversions
  merge(arr, temp, left, mid, right) {
    let i = left, j = mid + 1, k = left;
    let inv_count = 0;
    while (i <= mid && j <= right) {
      if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++]; // take from left half
      } else {
        temp[k++] = arr[j++]; // take from right half
        inv_count += (mid - i + 1); // count inversions
      }
    }
    while (i <= mid) temp[k++] = arr[i++]; // copy remaining left
    while (j <= right) temp[k++] = arr[j++]; // copy remaining right
    for (let idx = left; idx <= right; idx++) arr[idx] = temp[idx]; // copy back
    return inv_count;
  }

  // Recursive function to count inversions
  mergeSort(arr, temp, left, right) {
    let inv_count = 0;
    if (left < right) {
      let mid = Math.floor((left + right) / 2);
      inv_count += this.mergeSort(arr, temp, left, mid); // left half
      inv_count += this.mergeSort(arr, temp, mid + 1, right); // right half
      inv_count += this.merge(arr, temp, left, mid, right); // merge and count
    }
    return inv_count;
  }

  countInversions(arr) {
    let temp = new Array(arr.length);
    return this.mergeSort(arr, temp, 0, arr.length - 1);
  }
}

// Driver code
const arr = [2, 4, 1, 3, 5];
const counter = new CountInversions();
const result = counter.countInversions(arr);
console.log("Sorted array:", arr.join(" -> "));
console.log("Total inversions:", result);

if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count += (mid - i + 1); }

merge step: count inversions when right element is smaller than left

inv_count += this.mergeSort(arr, temp, left, mid); inv_count += this.mergeSort(arr, temp, mid + 1, right); inv_count += this.merge(arr, temp, left, mid, right);

recursive divide and conquer: count inversions in left, right, and merged parts

Output

Sorted array: 1 -> 2 -> 3 -> 4 -> 5

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 array used for merging

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 0 inversions without error

DSA Javascript

if (left < right) { ... }

array with one element

returns 0 inversions as no pairs exist

DSA Javascript

if (left < right) { ... }

array with all equal elements

returns 0 inversions since no element is greater than another

DSA Javascript

if (arr[i] <= arr[j]) { ... }

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 while sorting.

Common Mistakes

Mistake: Counting inversions only by comparing adjacent elements
Fix: Use merge sort to count all inversions, including non-adjacent pairs

Mistake: Not adding the correct number of inversions during merge step
Fix: Add (mid - i + 1) when right element is smaller than left to count all inversions caused by that element

Summary

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

Use it when you need to find how mixed up an array is efficiently.

The key insight is counting inversions during the merge step by knowing how many elements remain in the left half.

Practice

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

easy

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

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

C. The total number of elements in the array

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

   An inversion is when a larger number appears before a smaller number in the array.

2. Step 2: Compare options with the definition

   A pair of elements where the first is greater than the second and appears before it correctly describes this as a pair where the first element is greater and comes before the second.

3. Final Answer:

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

4. Quick Check:

   Inversion = pair (i, j) with i < j and arr[i] > arr[j] [OK]

Hint: Inversion means bigger number comes before smaller one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts pairs where first is smaller
• Mixing inversion with total elements count

2. Which of the following JavaScript code snippets correctly initializes a variable to count inversions?

easy

A. int count = 0;

B. count := 0;

C. let count = 0;

D. var count == 0;

Solution

1. Step 1: Identify correct JavaScript syntax for variable initialization

   JavaScript uses let or var with = for assignment.

2. Step 2: Check each option

   let count = 0; uses let count = 0; which is correct. count := 0; uses ':=' which is not JavaScript. int count = 0; uses 'int' which is not JavaScript. var count == 0; uses '==' which is a comparison, not assignment.

3. Final Answer:

   let count = 0; -> Option C

4. Quick Check:

   Variable assignment in JS uses =, not := or == [OK]

Hint: Use let or var with = for assignment in JavaScript [OK]

Common Mistakes:

• Using ':=' instead of '='
• Using 'int' keyword from other languages
• Using '==' instead of '=' for assignment

3. What is the number of inversions in the array [2, 4, 1, 3, 5]?

medium

A. 3

B. 2

C. 4

D. 5

Solution

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

   Check pairs where first element is greater and appears before second:
   - (2,1), (4,1), (4,3)

2. Step 2: Count the total inversions

   There are 3 such pairs.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Pairs (2,1), (4,1), (4,3) = 3 inversions [OK]

Hint: Count pairs where earlier number is bigger than later [OK]

Common Mistakes:

• Counting pairs where first is smaller
• Missing some inversion pairs
• Counting total pairs instead of inversions

4. Consider this code snippet to count inversions:

function countInversions(arr) {
  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;
}

What is the error in this code?

medium

A. The function should return arr.length instead of count

B. The inner loop should start from j = 0

C. The count variable should be initialized inside the loops

D. The comparison should be arr[i] > arr[j] to count inversions

Solution

1. Step 1: Understand the inversion condition

   An inversion is when arr[i] > arr[j] and i < j, but code checks arr[i] < arr[j].

2. Step 2: Identify the fix

   The comparison should be changed to arr[i] > arr[j] to count inversions correctly.

3. Final Answer:

   The comparison should be arr[i] > arr[j] to count inversions -> Option D

4. Quick Check:

   Inversion means first element bigger, so use > [OK]

Hint: Use > to detect inversion pairs, not < [OK]

Common Mistakes:

• Using < instead of > in condition
• Starting inner loop from 0 instead of i+1
• Resetting count inside loops

5. Given the array [8, 4, 2, 1], which approach will efficiently count the number of inversions?

hard

A. Sort the array and count inversions during merge (O(n log n) time)

B. Count inversions by summing all elements

C. Use a nested loop to compare all pairs (O(n²) time)

D. Use a hash map to store counts of elements

Solution

1. Step 1: Understand the problem size and efficiency

   For larger arrays, nested loops (O(n²)) are slow. Merge sort based counting is efficient (O(n log n)).

2. Step 2: Identify the best approach

   Counting inversions during merge sort is a classic efficient method.

3. Final Answer:

   Sort the array and count inversions during merge (O(n log n) time) -> Option A

4. Quick Check:

   Merge sort inversion count = efficient O(n log n) [OK]

Hint: Use merge sort to count inversions efficiently [OK]

Common Mistakes:

• Using nested loops for large arrays causing slow performance
• Trying to sum elements instead of counting pairs
• Using hash maps which don't help count inversions