Count Inversions in Array in DSA C++

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 by height. Every time a taller person stands before a shorter person, it counts as one inversion, like people not standing in height order.

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

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 smaller parts for easier counting

Step 2: Split left half further: 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: compare 2 and 4, no inversion

2 -> 4 (sorted)

Why: Two elements sorted, no inversion found

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

Merge steps:
Compare 2 and 1: 2 > 1 inversion found (count=2)
Result: 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,5] no inversion

3 -> 5 (sorted)

Why: Two elements sorted, no inversion found

Step 6: Merge left and right halves: merge [1,2,4] and [3,5], count inversions

Merge steps:
Compare 4 and 3: 4 > 3 inversion found (count=1)
Result: 1 -> 2 -> 3 -> 4 -> 5

Why: 3 is smaller than 4, so count inversion for this pair

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Merge two sorted halves and count inversions
long long merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    long long inv_count = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++]; // take from left
        } else {
            temp[k++] = arr[j++]; // take from right
            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 (int idx = 0; idx < temp.size(); idx++) {
        arr[left + idx] = temp[idx]; // copy back to original
    }

    return inv_count;
}

// Recursive merge sort that counts inversions
long long mergeSort(vector<int>& arr, int left, int right) {
    long long inv_count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        inv_count += mergeSort(arr, left, mid); // left half
        inv_count += mergeSort(arr, mid + 1, right); // right half
        inv_count += merge(arr, left, mid, right); // merge and count
    }
    return inv_count;
}

int main() {
    vector<int> arr = {2, 4, 1, 3, 5};
    long long result = mergeSort(arr, 0, arr.size() - 1);
    for (int num : arr) cout << num << " -> ";
    cout << "null" << endl;
    cout << "Total inversions: " << result << endl;
    return 0;
}

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 += mergeSort(arr, left, mid); inv_count += mergeSort(arr, mid + 1, right); inv_count += merge(arr, left, mid, right);

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

Output

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

Total inversions: 3

Complexity Analysis

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

Space: O(n) due to temporary arrays used 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 0 inversions without error

DSA C++

if (left < right) {

array with one element

returns 0 inversions as no pairs exist

DSA C++

if (left < right) {

array with all equal elements

returns 0 inversions as no element is greater than another

DSA C++

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 merge sort inversion counting because it efficiently counts while sorting.

Common Mistakes

Mistake: Counting inversions only during comparisons without merging properly
Fix: Count inversions during merge step by adding number of remaining elements in left half when right element is smaller

Summary

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

Use when you need to find how 'unsorted' 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. 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