Count Inversions in Array in DSA Typescript - Execution Trace

Concept Flow - Count Inversions in Array

Start with full array

↓

Divide array into two halves

↓

Recursively count inversions in left half

↓

Recursively count inversions in right half

↓

Merge two halves while counting split inversions

↓

Sum left + right + split inversions

↓

Return total inversion count

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

Execution Sample

DSA Typescript

function countInversions(arr: number[]): number {
  if (arr.length <= 1) return 0;
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return countInversions(left) + countInversions(right) + mergeCount(arr, left, right);
}

function mergeCount(arr: number[], left: number[], right: number[]): number {
  let i = 0, j = 0, k = 0, inversions = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      arr[k++] = left[i++];
    } else {
      arr[k++] = right[j++];
      inversions += left.length - i;
    }
  }
  while (i < left.length) {
    arr[k++] = left[i++];
  }
  while (j < right.length) {
    arr[k++] = right[j++];
  }
  return inversions;
}

This code counts inversions by splitting the array, counting in halves, and merging while counting cross inversions.

Execution Table

Step	Operation	Array Segment	Inversions Counted	Pointer Changes	Visual State
1	Start	[2, 4, 1, 3, 5]	0	head=0, mid=2	[2, 4, 1, 3, 5]
2	Divide	[2, 4]	0	left=[2,4], right=[1,3,5]	[2, 4] | [1, 3, 5]
3	Divide Left	[2, 4]	0	left=[2], right=[4]	[2] | [4]
4	Count Left Left	[2]	0	single element	[2]
5	Count Left Right	[4]	0	single element	[4]
6	Merge Left	[2,4]	0	i=0,j=0,k=0	[2, 4]
7	Divide Right	[1, 3, 5]	0	left=[1], right=[3,5]	[1] | [3, 5]
8	Count Right Left	[1]	0	single element	[1]
9	Divide Right Right	[3, 5]	0	left=[3], right=[5]	[3] | [5]
10	Count Right Right Left	[3]	0	single element	[3]
11	Count Right Right Right	[5]	0	single element	[5]
12	Merge Right Right	[3,5]	0	i=0,j=0,k=0	[3, 5]
13	Merge Right	[1,3,5]	0	i=0,j=0,k=0	[1, 3, 5]
14	Merge Full	[2,4,1,3,5]	3	i=0,j=0,k=0	[1, 2, 3, 4, 5]
15	End	[1, 2, 3, 4, 5]	3	completed	[1, 2, 3, 4, 5]

💡 All subarrays processed and merged; total inversions counted = 3

Variable Tracker

Variable	Start	After Step 6	After Step 13	After Step 14	Final
arr	[2,4,1,3,5]	[2,4]	[1,3,5]	[1,2,3,4,5]	[1,2,3,4,5]
inversions	0	0	0	3	3
left	[]	[2]	[1]	[1,2,3]	[1,2,3]
right	[]	[4]	[3,5]	[4,5]	[4,5]
i (left index)	0	1	1	2	2
j (right index)	0	1	2	3	3
k (merged index)	0	2	3	5	5

Key Moments - 3 Insights

Why do we count inversions during the merge step and not only in the recursive calls?

Because inversions can occur between elements in the left and right halves. The merge step compares these elements and counts such 'split' inversions, as shown in execution_table row 14.

Why does the array get sorted during counting inversions?

The merge step sorts the array segments while counting inversions. This sorting is necessary to efficiently count cross inversions and is visible in the Visual State column from step 6 to step 14.

How do pointer changes i, j, k help in counting inversions?

Pointers i and j track positions in left and right halves, k tracks merged array position. When element at right[j] is less than left[i], all remaining elements in left from i onwards form inversions, counted at step 14.

Visual Quiz - 3 Questions

Look at the execution_table at step 14. How many inversions are counted during the full merge?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Inversions Counted' column at step 14 in execution_table.

At which step does the array segment [3, 5] get merged and sorted?

A Step 13

B Step 9

C Step 12

D Step 14

💡 Hint

Look for the merge operation on [3, 5] in execution_table rows.

If the initial array was already sorted, how would the 'Inversions Counted' column change in the execution_table?

A All zeros

B Increase by 1 each merge

C Random values

D Only last step non-zero

💡 Hint

Recall that inversions count pairs where left element > right element; sorted array has none.

Concept Snapshot

Count Inversions in Array:
- Use divide and conquer (merge sort) approach
- Recursively count inversions in left and right halves
- Count split inversions during merge step
- Sum all counts for total inversions
- Array gets sorted as a side effect
- Efficient O(n log n) time complexity

Full Transcript

Counting inversions in an array means finding how many pairs of elements are out of order. We use a divide and conquer method similar to merge sort. The array is split into halves recursively. We count inversions inside each half and also count inversions between halves during the merge step. The merge step sorts the array segment and counts how many elements from the left half are greater than elements from the right half. The total inversion count is the sum of left, right, and split inversions. This method is efficient and sorts the array as a side effect.

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