Count Inversions in Array in DSA Java

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's like an inversion. Counting all these pairs tells us how 'mixed up' the line is.

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 by counting inversions in smaller parts

Step 2: Split left half into [2,4] and [1]

Left-left: 2 -> 4
Left-right: 1

Why: Further divide to count inversions in smaller arrays

Step 3: Count inversions in [2,4]: no inversions because 2 < 4

2 -> 4 (0 inversions)

Why: Base case: small sorted array has zero inversions

Step 4: Count inversions in [1]: single element, zero inversions

1 (0 inversions)

Why: Single element array has no inversions

Step 5: Merge [2,4] and [1], count split inversions: 2 > 1 and 4 > 1, so 2 inversions

Merged: 1 -> 2 -> 4 (2 inversions)

Why: Count pairs where left half elements are bigger than right half elements

Step 6: Count inversions in right half [3,5]: no inversions because 3 < 5

3 -> 5 (0 inversions)

Why: Sorted small array has zero inversions

Step 7: Merge left [1,2,4] and right [3,5], count split inversions: 4 > 3, so 1 inversion

Merged: 1 -> 2 -> 3 -> 4 -> 5 (1 inversion)

Why: Count pairs crossing halves where left element is bigger

Result:

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

Annotated Code

DSA Java

public class CountInversions {
    public static long mergeSortAndCount(int[] arr, int left, int right) {
        long count = 0;
        if (left < right) {
            int mid = left + (right - left) / 2;
            count += mergeSortAndCount(arr, left, mid); // count left side inversions
            count += mergeSortAndCount(arr, mid + 1, right); // count right side inversions
            count += mergeAndCount(arr, left, mid, right); // count split inversions
        }
        return count;
    }

    public static long mergeAndCount(int[] arr, int left, int mid, int right) {
        int[] leftArr = new int[mid - left + 1];
        int[] rightArr = new int[right - mid];

        for (int i = 0; i < leftArr.length; i++)
            leftArr[i] = arr[left + i];
        for (int i = 0; i < rightArr.length; i++)
            rightArr[i] = arr[mid + 1 + i];

        int i = 0, j = 0, k = left;
        long swaps = 0;

        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++]; // take from left
            } else {
                arr[k++] = rightArr[j++]; // take from right
                swaps += (leftArr.length - i); // count inversions
            }
        }

        while (i < leftArr.length) {
            arr[k++] = leftArr[i++]; // copy remaining left
        }

        while (j < rightArr.length) {
            arr[k++] = rightArr[j++]; // copy remaining right
        }

        return swaps;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 1, 3, 5};
        long result = mergeSortAndCount(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " -> ");
        }
        System.out.println("null");
        System.out.println("Total inversions: " + result);
    }
}

count += mergeSortAndCount(arr, left, mid); // count left side inversions

recursively count inversions in left half

count += mergeSortAndCount(arr, mid + 1, right); // count right side inversions

recursively count inversions in right half

count += mergeAndCount(arr, left, mid, right); // count split inversions

count inversions where left half elements are bigger than right half

if (leftArr[i] <= rightArr[j]) { arr[k++] = leftArr[i++]; // take from left } else { arr[k++] = rightArr[j++]; // take from right swaps += (leftArr.length - i); // count inversions }

merge arrays and count how many left elements are bigger than right elements

Output

Sorted array:

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 arrays used during 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 Java

if (left < right) {

array with one element

returns 0 inversions as no pairs exist

DSA Java

if (left < right) {

array with all equal elements

returns 0 inversions since no element is greater than another

DSA Java

if (leftArr[i] <= rightArr[j]) {

When to Use This Pattern

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

Common Mistakes

Mistake: Counting inversions only within halves and forgetting to count split inversions during merge
Fix: Add counting logic in the merge step to include pairs crossing the halves

Mistake: Not copying remaining elements after merging, causing incorrect array state
Fix: Ensure to copy leftover elements from both halves after main merge loop

Summary

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

Use it when you need to measure how unsorted an array is efficiently.

The key insight is counting inversions during the merge step while sorting.

Practice

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

easy

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

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. 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 correctly describes this as a pair where the first element is greater and comes before the second.

3. Final Answer:

   A -> Option A

4. Quick Check:

   Inversion = pair (i, j) with i < j and arr[i] > arr[j] [OK]

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

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal elements
• Mixing up element positions

2. Which of the following Java code snippets correctly initializes an integer array named arr with values 3, 1, 2?

easy

A. int arr = {3, 1, 2};

B. int[] arr = new int(3, 1, 2);

C. int[] arr = {3, 1, 2};

D. int arr[] = new int[3];

Solution

1. Step 1: Check array declaration syntax

   In Java, arrays are declared with square brackets and initialized with curly braces or using new keyword with curly braces.

2. Step 2: Validate each option

   int[] arr = {3, 1, 2}; uses correct syntax: int[] arr = {3, 1, 2}; int arr = {3, 1, 2}; misses brackets, int[] arr = new int(3, 1, 2); uses wrong constructor syntax, int arr[] = new int[3]; does not initialize to the given values (zeros instead).

3. Final Answer:

   B -> Option C

4. Quick Check:

   Correct array init = int[] arr = {3, 1, 2}; [OK]

Hint: Use int[] arr = {values}; to initialize arrays [OK]

Common Mistakes:

• Missing square brackets in declaration
• Using parentheses instead of braces
• Incorrect use of new keyword

3. What is the number of inversions in the array [2, 4, 1, 3, 5]?

medium

A. 2

B. 5

C. 4

D. 3

Solution

1. Step 1: Identify all inversion pairs

   Pairs where first element is greater and appears before second: (2,1), (4,1), (4,3), (4,5) is not inversion, (3,5) no inversion. Actually, count carefully: (2,1), (4,1), (4,3) are 3 inversions. But check if (2,3) or (2,5) are inversions? No. So total 3 inversions.

2. Step 2: Count the pairs

   Counting these pairs gives 3 inversions.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Inversions in [2,4,1,3,5] = 3 [OK]

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

Common Mistakes:

• Counting pairs with equal elements
• Missing some inversion pairs
• Counting sorted pairs as inversions

4. Consider the following Java method to count inversions. What is the error?

public static int countInversions(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] < arr[j]) {
                count++;
            }
        }
    }
    return count;
}

medium

A. The comparison should be arr[i] > arr[j] to count inversions

B. The inner loop should start from j = 0

C. The count variable should be initialized inside the loops

D. The method should return void instead of int

Solution

1. Step 1: Analyze the inversion condition

   Inversion means arr[i] > arr[j] where i < j, but code checks arr[i] < arr[j], which is incorrect.

2. Step 2: Identify the fix

   Change condition to arr[i] > arr[j] to correctly count inversions.

3. Final Answer:

   The comparison should be arr[i] > arr[j] to count inversions -> Option A

4. Quick Check:

   Correct condition = arr[i] > arr[j] [OK]

Hint: Inversion means left element greater than right [OK]

Common Mistakes:

• Using wrong comparison operator
• Starting inner loop incorrectly
• Resetting count inside loops

5. Given the array [8, 4, 2, 1], what is the total number of inversions? Also, explain why this number is significant in sorting algorithms.

hard

A. 6; It shows the array is nearly sorted

B. 6; It shows the array is sorted in descending order

C. 4; It shows the array is sorted in ascending order

D. 3; It shows the array has few inversions

Solution

1. Step 1: Count inversions in the array

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

2. Step 2: Understand significance in sorting

   Maximum inversions mean array is sorted in descending order, which is worst case for some sorting algorithms.

3. Final Answer:

   6; It shows the array is sorted in descending order -> Option B

4. Quick Check:

   Inversions = 6; descending order = max inversions [OK]

Hint: Max inversions = descending order array [OK]

Common Mistakes:

• Miscounting inversion pairs
• Confusing max inversions with sorted array
• Ignoring significance in sorting