Count Inversions in Array in DSA C++ - Execution Trace

Concept Flow - Count Inversions in Array

Start with 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, and split inversions

↓

Return total inversion count

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

Execution Sample

DSA C++

int mergeCount(int arr[], int temp[], int left, int right) {
  int mid = (left + right) / 2;
  int i = left, j = mid + 1, k = left, inv_count = 0;
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) temp[k++] = arr[i++];
    else { temp[k++] = arr[j++]; inv_count += (mid - i + 1); }
  }
  while (i <= mid) temp[k++] = arr[i++];
  while (j <= right) temp[k++] = arr[j++];
  for (int idx = left; idx <= right; idx++) arr[idx] = temp[idx];
  return inv_count;
}

int mergeSortCount(int arr[], int temp[], int left, int right) {
  int inv_count = 0;
  if (left < right) {
    int mid = (left + right) / 2;
    inv_count += mergeSortCount(arr, temp, left, mid);
    inv_count += mergeSortCount(arr, temp, mid + 1, right);
    inv_count += mergeCount(arr, temp, left, right);
  }
  return inv_count;
}

This code counts inversions by recursively splitting the array and merging while counting cross-inversions.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with full array	[2, 4, 1, 3, 5]	head points to index 0	2 -> 4 -> 1 -> 3 -> 5
2	Divide array into left half	[2, 4, 1]	left=0, right=2	2 -> 4 -> 1
3	Divide left half into left half	[2, 4]	left=0, right=1	2 -> 4
4	Divide [2,4] into single elements	[2], [4]	left=0, right=0 and left=1, right=1	2 and 4 separate
5	Merge [2] and [4], count inversions	[2,4]	i=0, j=1, k=0	2 -> 4 (no inversion)
6	Divide right half of left half	[1]	left=2, right=2	1
7	Merge [2,4] and [1], count split inversions	[1,2,4]	i=0, j=2, k=0	1 -> 2 -> 4 (2 inversions: (2,1), (4,1))
8	Divide right half of full array	[3,5]	left=3, right=4	3 -> 5
9	Divide [3,5] into single elements	[3], [5]	left=3, right=3 and left=4, right=4	3 and 5 separate
10	Merge [3] and [5], count inversions	[3,5]	i=3, j=4, k=3	3 -> 5 (no inversion)
11	Merge [1,2,4] and [3,5], count split inversions	[1,2,3,4,5]	i=0, j=3, k=0	1 -> 2 -> 3 -> 4 -> 5 (1 inversion: (4,3))
12	Total inversions = left + right + split	3 inversions	Sum of 2 + 0 + 1	Final sorted array: 1 -> 2 -> 3 -> 4 -> 5
13	Exit	No more splits	Completed merge sort	Sorted array with inversion count

💡 All subarrays merged and counted, total inversions found = 3

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 10	After Step 11	Final
arr	[2,4,1,3,5]	[2,4,1,3,5]	[1,2,4,3,5]	[1,2,4,3,5]	[1,2,3,4,5]	[1,2,3,4,5]
inv_count	0	0	2	2	3	3
i (left pointer)	0	0	0	3	0	N/A
j (right pointer)	3	3	2	4	3	N/A
k (temp index)	0	2	2	4	4	N/A

Key Moments - 3 Insights

Why do we add (mid - i + 1) to inversion count when arr[i] > arr[j] during merge?

Because all elements from i to mid are greater than arr[j], so each forms an inversion. See execution_table step 7 where 2 inversions are counted at once.

Why do we merge sorted halves instead of counting inversions directly?

Merging sorted halves lets us count split inversions efficiently by comparing elements in order, avoiding checking all pairs. Refer to steps 5, 7, and 11 in execution_table.

What happens if the array is already sorted?

No inversions are counted during merge because arr[i] <= arr[j] always holds, so inv_count stays zero. This is shown in step 5 and 10 where no inversions are added.

Visual Quiz - 3 Questions

Look at the execution_table, what is the inversion count after merging [2,4] and [1] at step 7?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Operation' and 'Visual State' columns at step 7 in execution_table.

At which step does the total inversion count reach 3?

A Step 11

B Step 10

C Step 12

D Step 7

💡 Hint

Look at the 'inv_count' variable in variable_tracker after step 12.

If the array was already sorted, how would the inversion count change at step 5?

A It would remain 0

B It would decrease

C It would increase by 1

D It would double

💡 Hint

Refer to key_moments about no inversions counted when arr[i] <= arr[j].

Concept Snapshot

Count Inversions in Array using Merge Sort:
- Split array into halves recursively
- Count inversions in left and right halves
- Count split inversions during merge
- Sum all counts for total inversions
- Efficient O(n log n) method vs O(n^2) naive

Full Transcript

Counting inversions in an array means finding how many pairs of elements are out of order. We use a merge sort approach: split the array into halves, count inversions in each half, then count inversions between halves while merging. During merge, when an element from the right half is smaller than one from the left, it forms inversions with all remaining elements in the left half. We add these counts and continue merging until the whole array is sorted. This method is efficient and counts all inversions correctly.

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 (i, j) such that i < j and 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 matches the definition exactly, others describe different 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 with first > second [OK]

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

Common Mistakes:

• Confusing inversion with sorted pairs
• Thinking inversion counts total elements
• Mixing up greater and smaller conditions

2. Which of the following C++ code snippets correctly declares a function to count inversions in an array?

easy

A. int countInversions(vector<int>& arr);

B. void countInversions(vector<int> arr);

C. int countInversions(int arr[]);

D. int countInversions(vector<int> arr);

Solution

1. Step 1: Check function return type and parameter passing

   The function should return an integer count and take array by reference for efficiency.

2. Step 2: Analyze each option

   int countInversions(vector<int>& arr); returns int and takes vector by reference, correct. void countInversions(vector<int> arr); returns void, wrong. int countInversions(int arr[]); uses raw array without size info, less preferred. int countInversions(vector<int> arr); passes vector by value, inefficient.

3. Final Answer:

   int countInversions(vector<int>& arr); -> Option A

4. Quick Check:

   Return int, pass vector by reference [OK]

Hint: Count returns int; pass vector by reference to avoid copying [OK]

Common Mistakes:

• Using void return type
• Passing vector by value causing copies
• Using raw arrays without size info

3. What is the output of the following C++ code snippet?

std::vector<int> arr = {2, 4, 1, 3, 5};
int count = 0;
for (int i = 0; i < arr.size(); i++) {
  for (int j = i + 1; j < arr.size(); j++) {
    if (arr[i] > arr[j]) count++;
  }
}
std::cout << count << std::endl;

medium

A. 2

B. 4

C. 3

D. 5

Solution

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

   Pairs where first > second and first index < second index are: (2,1), (4,1), (4,3).

2. Step 2: Count these pairs

   There are exactly 3 such pairs.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Inversions = 3 [OK]

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

Common Mistakes:

• Counting pairs where first is smaller
• Missing some inversion pairs
• Confusing index order

4. Find the error in this C++ function to count inversions using a brute force approach:

int countInversions(std::vector<int> arr) {
  int count = 0;
  for (int i = 0; i < arr.size(); i++) {
    for (int j = 0; j < arr.size(); j++) {
      if (arr[i] > arr[j]) count++;
    }
  }
  return count;
}

medium

A. Function should return void, not int

B. Inner loop should start from j = i + 1, not 0

C. Comparison should be arr[i] < arr[j]

D. Count variable should be initialized outside the function

Solution

1. Step 1: Analyze loop ranges for counting inversions

   Inversion pairs require i < j, so inner loop must start from j = i + 1.

2. Step 2: Identify the error in the given code

   Inner loop starts from 0, counting pairs twice and including invalid pairs where j < i.

3. Final Answer:

   Inner loop should start from j = i + 1, not 0 -> Option B

4. Quick Check:

   Inner loop from i+1 to end [OK]

Hint: Inner loop must start after outer index to avoid double count [OK]

Common Mistakes:

• Starting inner loop from 0 causing double counting
• Wrong comparison direction
• Incorrect return type

5. Given the array {8, 4, 2, 1}, what is the number of inversions using an efficient merge sort based approach?

hard

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Understand inversions in the array

   All pairs where first > second and first index < second index are: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1).

2. Step 2: Count inversions carefully

   There are 6 pairs total, but merge sort counts inversions during merging. The efficient approach counts 6 inversions.

3. Step 3: Verify merge sort inversion count

   Merge sort counts 6 inversions for this array.

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Inversions = 6 [OK]

Hint: Count pairs where left element is bigger during merge [OK]

Common Mistakes:

• Under-counting inversions by missing pairs
• Confusing brute force and merge sort counts
• Miscounting pairs with equal elements