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 waiting by height. Every time a taller person stands before a shorter person, it counts as a mix-up or inversion.

Array: [2, 4, 1, 3, 5]
Indices:  0  1  2  3  4
Inversions: pairs like (2,1), (4,1), (4,3)

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 further: left_left=[2,4], left_right=[1]

left_left: [2,4]
left_right: [1]

Why: Keep splitting until subarrays have one element

Step 3: Count inversions in left_left by merging [2] and [4]

merged left_left: [2,4], inversions=0

Why: No inversion since 2 < 4

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

merged left: [1,2,4], inversions=2 (pairs: (2,1), (4,1))

Why: 1 is smaller than 2 and 4, so two inversions

Step 5: Count inversions in right half by merging [3] and [5]

merged right: [3,5], inversions=0

Why: No inversion since 3 < 5

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

merged full: [1,2,3,4,5], inversions=1 (pair: (4,3))

Why: 4 is before 3, so one inversion

Result:

Final merged array: [1,2,3,4,5]
Total inversions: 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Merge two sorted halves and count inversions
long long merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left;    // start of left subarray
    int j = mid + 1; // start of right subarray
    int k = left;    // start of temp array
    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 = left; idx <= right; idx++) {
        arr[idx] = temp[idx]; // copy back to original
    }

    return inv_count;
}

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

int main() {
    int arr[] = {2, 4, 1, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int *temp = (int *)malloc(n * sizeof(int));
    long long result = mergeSort(arr, temp, 0, n - 1);
    free(temp);

    // Print sorted array
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(" -> ");
    }
    printf(" -> null\n");

    // Print inversion count
    printf("Total inversions: %lld\n", result);
    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, temp, left, mid); inv_count += mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid, right);

divide array, count inversions in halves and merge step

Output

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

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 C

if (left < right) { ... } in mergeSort

array with one element

returns 0 inversions as no pairs exist

DSA C

if (left < right) { ... } in mergeSort

array with all equal elements

returns 0 inversions since no element is greater than another

DSA C

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

When to Use This Pattern

When asked to count how many pairs are out of order in an array efficiently, use the merge sort inversion counting pattern because it counts while sorting.

Common Mistakes

Mistake: Counting inversions only by comparing adjacent elements
Fix: Use merge step to count all cross inversions between halves, not just adjacent pairs

Mistake: Not copying merged elements back to original array
Fix: After merging, copy temp array back to original to keep array sorted for next merges

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 of merge sort.

Practice

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

easy

A. The total number of elements in the array

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

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

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 definition

   A pair of elements where the first is greater than the second and appears before it matches this 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 B

4. Quick Check:

   Inversion = larger before smaller [OK]

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

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal elements
• Mixing inversion with total pairs

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

easy

A. int countInversions(int arr[], int n);

B. void countInversions(int arr[], int n);

C. int countInversions(int arr, int n[]);

D. int countInversions(int *arr, int n[]);

Solution

1. Step 1: Check function signature correctness

   The function should return an integer count and take an integer array and its size as parameters.

2. Step 2: Analyze each option

   int countInversions(int arr[], int n); correctly uses int return type and parameters as int arr[] and int n. Others have wrong parameter types or return type.

3. Final Answer:

   int countInversions(int arr[], int n); -> Option A

4. Quick Check:

   Correct function signature returns int and takes int array and size [OK]

Hint: Function returns int and takes int array plus size [OK]

Common Mistakes:

• Using void return type instead of int
• Swapping array and size parameter types
• Using pointer syntax incorrectly

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

int arr[] = {2, 4, 1, 3, 5};
int n = 5;
int count = 0;
for(int i = 0; i < n-1; i++) {
  for(int j = i+1; j < n; j++) {
    if(arr[i] > arr[j]) count++;
  }
}
printf("%d", count);

medium

A. 5

B. 4

C. 3

D. 2

Solution

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

   Pairs where first element is greater than second: (2,1), (4,1), (4,3). Total = 3.

2. Step 2: Confirm count variable increments correctly

   Nested loops check all pairs; count increments for each inversion found, total 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Inversions = 3 [OK]

Hint: Count pairs where left element > right element [OK]

Common Mistakes:

• Counting pairs where left < right
• Missing some inversion pairs
• Off-by-one errors in loops

4. The following code is intended to count inversions but has a bug. What is the bug?

int countInversions(int arr[], int n) {
  int count = 0;
  for(int i = 0; i < n; i++) {
    for(int j = i; j < n; j++) {
      if(arr[i] >= arr[j]) count++;
    }
  }
  return count;
}

medium

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

B. The count variable should be initialized outside the function

C. The comparison should be arr[i] < arr[j]

D. The function should return void instead of int

Solution

1. Step 1: Analyze loop ranges for counting pairs

   Inner loop starts at j = i, so it compares arr[i] with itself, causing incorrect counting.

2. Step 2: Correct inner loop start index

   Inner loop should start at j = i + 1 to avoid self-comparison.

3. Final Answer:

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

4. Quick Check:

   Start inner loop at i+1 to avoid self-comparison [OK]

Hint: Inner loop must start after outer loop index [OK]

Common Mistakes:

• Starting inner loop at same index as outer
• Wrong comparison operator
• Returning wrong type

5. Given the array {8, 4, 2, 1}, what is the total number of inversions? Also, explain why this number represents the worst case for inversion counting.

hard

A. 4

B. 0

C. 3

D. 6

Solution

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

   Pairs: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) total 6 inversions.

2. Step 2: Understand why this is worst case

   The array is sorted in descending order, so every pair is inverted, maximum inversions possible for size 4.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Descending order array has max inversions = n(n-1)/2 [OK]

Hint: Descending order array has max inversions n(n-1)/2 [OK]

Common Mistakes:

• Counting only adjacent inversions
• Forgetting pairs with elements far apart
• Confusing inversion count with array length