Count Inversions in Array in DSA Javascript - Execution Trace

Concept Flow - Count Inversions in Array

Start with array

↓

Divide array into halves

↓

Recursively count inversions in left half

↓

Recursively count inversions in right half

↓

Merge two halves while counting cross inversions

↓

Sum left + right + cross inversions

↓

Return total inversions

The array is split into halves recursively, counting inversions inside each half and across halves during merge, then sums all counts.

Execution Sample

DSA Javascript

function mergeSort(arr) {
  if (arr.length <= 1) return {sorted: arr, count: 0};
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  let i = 0, j = 0, count = 0, sorted = [];
  while (i < left.sorted.length && j < right.sorted.length) {
    if (left.sorted[i] <= right.sorted[j]) {
      sorted.push(left.sorted[i++]);
    } else {
      sorted.push(right.sorted[j++]);
      count += left.sorted.length - i;
    }
  }
  return {sorted: sorted.concat(left.sorted.slice(i)).concat(right.sorted.slice(j)), count: left.count + right.count + count};
}

This code counts inversions by recursively sorting and merging while counting cross inversions.

Execution Table

Step	Operation	Array State	Pointer Changes	Inversions Counted	Visual State
1	Start with full array	[2, 4, 1, 3, 5]	head=0, mid=2, tail=4	0	2 -> 4 -> 1 -> 3 -> 5 -> null
2	Divide left half	[2, 4]	head=0, mid=1, tail=1	0	2 -> 4 -> null
3	Divide left half further	[2]	single element	0	2 -> null
4	Divide right half further	[4]	single element	0	4 -> null
5	Merge left halves	[2,4]	i=0, j=0	0	2 -> 4 -> null
6	Divide right half	[1, 3, 5]	head=2, mid=3, tail=4	0	1 -> 3 -> 5 -> null
7	Divide right half left	[1, 3]	head=2, mid=2, tail=3	0	1 -> 3 -> null
8	Divide right half left further	[1]	single element	0	1 -> null
9	Divide right half right further	[3]	single element	0	3 -> null
10	Merge right half left	[1,3]	i=0, j=0	0	1 -> 3 -> null
11	Divide right half right	[5]	single element	0	5 -> null
12	Merge right halves	[1,3,5]	i=0, j=0	0	1 -> 3 -> 5 -> null
13	Merge full halves	[1,2,3,4,5]	i=0, j=0	3	1 -> 2 -> 3 -> 4 -> 5 -> null
14	Total inversions	Final sorted array	N/A	3	1 -> 2 -> 3 -> 4 -> 5 -> null
15	Exit	All merges done	N/A	3	Sorted array with inversion count 3

💡 All subarrays merged and counted, total inversions = 3

Variable Tracker

Variable	Start	After Step 5	After Step 12	After Step 13	Final
arr	[2,4,1,3,5]	[2,4]	[1,3,5]	[1,2,3,4,5]	[1,2,3,4,5]
count	0	0	0	3	3
i (left index)	0	0	0	varies	varies
j (right index)	0	0	0	varies	varies

Key Moments - 3 Insights

Why do we count inversions only when left element is greater than right during merge?

Because during merge, left and right halves are sorted. If left[i] > right[j], all remaining elements from left[i] onwards form inversions with right[j]. This is shown in step 13 where count increases by left.sorted.length - i.

Why do we split the array recursively instead of checking all pairs directly?

Recursive splitting allows counting inversions efficiently in O(n log n) time by merging sorted halves, unlike direct pair checking which is O(n²). This is reflected in steps 2-12 where array is divided and merged.

What does the 'count' variable represent at each merge step?

It represents the number of inversions found between the two halves being merged. For example, at step 13, count is 3, meaning 3 cross-inversions found during merging.

Visual Quiz - 3 Questions

Look at the execution table at step 13, how many inversions are counted during the final merge?

A 5

B 0

C 3

D 2

💡 Hint

Check the 'Inversions Counted' column at step 13 in the execution table.

At which step does the array become fully sorted?

A Step 13

B Step 5

C Step 12

D Step 10

💡 Hint

Look at the 'Array State' column and find when the array is sorted completely.

If the input array was already sorted, how would the inversion count change in the final step?

A It would be the same as 3

B It would be zero

C It would be maximum

D It would be negative

💡 Hint

Refer to the 'count' variable in variable_tracker and understand what inversion means.

Concept Snapshot

Count Inversions in Array:
- Use divide and conquer (merge sort) approach
- Recursively split array into halves
- Count inversions inside halves and across halves during merge
- Inversions counted when left element > right element during merge
- Time complexity: O(n log n)
- Returns total number of inversions in array

Full Transcript

Counting inversions in an array means finding how many pairs of elements are out of order. We use a method like merge sort: split the array into halves, count inversions in each half, then count inversions between halves while merging. During merge, if an element in the left half is greater than an element in the right half, it means all remaining elements in left half form inversions with that right element. We add these counts up. This method is efficient and sorts the array while counting. The example array [2,4,1,3,5] has 3 inversions counted during the final merge step. If the array was already sorted, the inversion count would be zero.

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