Count Inversions in an Array | Brute and Optimal

An inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted, the inversion count is 0. If the array is sorted in reverse order, the inversion count is at its maximum. This guide explores both the Brute Force (O(N²)) and Optimal (O(N log N)) approaches using a modified Merge Sort algorithm.

1. What is an Inversion? (Problem Definition)

An inversion is a pair of indices (i, j) in an array of integers such that:

1. i < j (the left element appears before the right element)
2. A[i] > A[j] (the left element is strictly greater than the right element)

Real-Life Analogy

Imagine organizing a bookshelf or a line of people by height. Every time a taller person is standing in front of (to the left of) a shorter person, that represents an "out of order" pair—an inversion. Your goal is to count how many such disordered pairs exist across the entire array without necessarily sorting it first (though sorting gives us the key to counting them efficiently).

Concrete Example

Consider the array: [5, 3, 2, 4, 1]

Let's find all valid pairs (A[i], A[j]) where A[i] > A[j] and i < j:

• Pairs starting with 5: (5, 3), (5, 2), (5, 4), (5, 1) -> 4 pairs
• Pairs starting with 3: (3, 2), (3, 1) -> 2 pairs
• Pairs starting with 2: (2, 1) -> 1 pair
• Pairs starting with 4: (4, 1) -> 1 pair

Total Inversion Count = 4 + 2 + 1 + 1 = 8.

2. The Naive Brute Force Approach

The most direct way to solve this problem is to inspect every possible pair in the array using nested loops.

Algorithm Logic

1. Initialize a count variable to 0.
2. Run an outer loop i from 0 to n - 1.
3. Run an inner loop j from i + 1 to n - 1 (to guarantee that the left element comes before the right element).
4. If A[i] > A[j], increment count++.
5. Return count.

Code Implementation (Python)

def countInversionsBrute(arr):
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                count += 1
    return count

Complexity Analysis

• Time Complexity: $O(N^2)$ because we examine roughly $\frac{N(N-1)}{2}$ pairs.
• Space Complexity: $O(1)$ auxiliary space as no extra data structures are used.

Note: An $O(N^2)$ solution is usually unacceptable to interviewers when working with large arrays ($N \ge 10^5$), prompting the need for an optimal divide-and-conquer strategy.

3. Core Mental Model: Counting Across Two Sorted Subarrays

Before jumping into the full Merge Sort modification, analyze what happens if you are given two separate sorted arrays and need to find how many pairs can be formed where the left element comes from Array 1 and the right element comes from Array 2.

Example Scenario

• Left Sorted Array: [2, 3, 5]
• Right Sorted Array: [2, 4]

Instead of comparing every element of Array 1 with every element of Array 2 ($O(N \times M)$), we can use two pointers taking advantage of the sorted property.

The Sorted Array Shortcut

Suppose pointer i points to 3 in the left array, and pointer j points to 2 in the right array:

• Is 3 > 2? Yes.
• Because the left array is sorted, every element to the right of 3 (e.g., 5) must also be greater than 2.
• Therefore, instead of adding 1 to our count, we can instantly add all remaining elements from 3 to the end of the left array in a single calculation!

4. Step-by-Step Evolution: Integrating with Merge Sort

We can achieve an optimal $O(N \log N)$ time complexity by integrating our counting logic directly into the Merge Sort algorithm.

Merge sort recursively divides the array into halves until each subarray has 1 element (which is inherently sorted). As the recursion unwinds, it merges two sorted halves back together. This merge step is where we count inversions.

Recursive Division Flow

5. The Merge-and-Count Algorithm

During the merge phase of Merge Sort, we have two sorted halves:

• Left Subarray: Low to Mid
• Right Subarray: Mid + 1 to High

Core Counting Rule in Merge

When comparing element Left[i] with Right[j]:

• If Left[i] <= Right[j]: No inversion. Move i forward.
• If Left[i] > Right[j]: Every element from index i to Mid in the left subarray is greater than Right[j].
  • Number of valid pairs = (Mid - i + 1)
  • Add this value to our inversion count.
  • Move j forward.

6. Complete Code Implementation (Java)

Here is the complete implementation of Count Inversions using Merge Sort in Java, avoiding global variables to follow production-grade coding standards.

public class CountInversions {

    public static long countInversions(long[] arr) {
        return mergeSort(arr, 0, arr.length - 1);
    }

    private static long mergeSort(long[] arr, int low, int high) {
        long count = 0;
        if (low >= high) return count;
        
        int mid = low + (high - low) / 2;
        
        // Count inversions in the left half
        count += mergeSort(arr, low, mid);
        // Count inversions in the right half
        count += mergeSort(arr, mid + 1, high);
        // Count cross-inversions during the merge step
        count += merge(arr, low, mid, high);
        
        return count;
    }

    private static long merge(long[] arr, int low, int mid, int high) {
        long[] temp = new long[high - low + 1];
        int left = low;      // Starting index of left half
        int right = mid + 1; // Starting index of right half
        int index = 0;
        long count = 0;

        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp[index++] = arr[left++];
            } else {
                // arr[left] > arr[right], meaning all elements from left to mid form inversions
                temp[index++] = arr[right++];
                count += (mid - left + 1);
            }
        }

        // Copy remaining elements from left half, if any
        while (left <= mid) {
            temp[index++] = arr[left++];
        }

        // Copy remaining elements from right half, if any
        while (right <= high) {
            temp[index++] = arr[right++];
        }

        // Transfer sorted elements back into original array
        for (int i = 0; i < temp.length; i++) {
            arr[low + i] = temp[i];
        }

        return count;
    }
}

7. Real-World Practical Pitfalls & Interview Edge Cases

When presenting this solution in an engineering interview, keep these considerations in mind:

Summary and Key Takeaways

• Problem Core: An inversion counts pairs (i, j) where i < j and A[i] > A[j].
• Brute Force Limitation: Nested loops check all pairs in $O(N^2)$ time, which fails for large datasets.
• Optimal Paradigm: Leverage Merge Sort to divide and conquer, identifying cross-inversions in linear time during the merge phase.
• The Shortcut Formula: When Left[i] > Right[j], all remaining elements in the left subarray (Mid - i + 1) form valid inversions with Right[j].
• Time Complexity: Reduced from $O(N^2)$ to $O(N \log N)$.
• Space Complexity: $O(N)$ auxiliary space required for the temporary merging array.
• Interview Communication: Explicitly mention data mutation side effects and integer overflow risks to earn top marks from interviewers.