Count Inversions in an Array | Brute and Optimal

Counting inversions in an array is a classic algorithmic problem that tests your ability to optimize from an inefficient $O(N^2)$ brute-force approach down to an optimal $O(N \log N)$ divide-and-conquer solution using Merge Sort. An inversion occurs when two elements in an array are out of their natural ascending order—meaning the left element is strictly greater than the right element (A[i] > A[j] where i < j).

1. Problem Statement & Definition of an Inversion

What is an Inversion?

Given an array of integers, an inversion is defined as a pair of indices (i, j) 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)

Concrete Example Walkthrough

Consider the array:

A = [5, 3, 2, 4, 1]

Let's identify all valid inversion pairs where A[i] > A[j] and i < j:

• Pairs starting with 5: (5, 3), (5, 2), (5, 4), (5, 1) $\rightarrow$ 4 pairs
• Pairs starting with 3: (3, 2), (3, 1) $\rightarrow$ 2 pairs
• Pairs starting with 2: (2, 1) $\rightarrow$ 1 pair
• Pairs starting with 4: (4, 1) $\rightarrow$ 1 pair

Total Inversion Count = $4 + 2 + 1 + 1 = \mathbf{8}$ pairs.

Note: The problem asks us to return the count of such pairs, not the actual pairs themselves.

2. The Naive Brute-Force Approach

When presented with this problem in an interview, the most intuitive starting point is checking every possible pair.

Algorithm Design

• Run an outer loop i from 0 to n - 1.
• Run an inner loop j from i + 1 to n - 1 (since j must be strictly to the right of i).
• Check if A[i] > A[j]. If true, increment our counter.

Naive Code Implementation (Java Style)

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

Complexity Analysis

• Time Complexity: $\mathcal{O}(N^2)$ because we examine every possible pair in nested loops.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space since we only use a counter variable.

Interview Reality: An $\mathcal{O}(N^2)$ solution will quickly result in a Time Limit Exceeded (TLE) error for large arrays ($N \ge 10^5$). The interviewer will immediately prompt you to optimize this down to $\mathcal{O}(N \log N)$.

3. Core Mental Model: The Sorted Subarrays Insight

Before jumping straight into Merge Sort, let's analyze a specialized sub-problem that reveals the optimal pattern.

Sub-Problem Setup

Imagine you are given two separate arrays, both of which are already sorted in ascending order:

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

We want to count how many pairs (left_element, right_element) satisfy left_element > right_element.

Real-Life Analogy & Two-Pointer Logic

Instead of comparing every single element in a brute-force manner, we use two pointers (one on the left array, one on the right array) taking advantage of the fact that both arrays are already sorted.

Left Array (Sorted):   [2, 3, 5]
                           ^ (pointer i)

Right Array (Sorted):  [2, 3, 4, 6]
                       ^ (pointer j)

• Step 1: Compare arr1[i] (2) with arr2[j] (2). Is 2 > 2? No. So advance j.
• Step 2: Compare arr1[i] (3) with arr2[j] (2). Is 3 > 2? Yes!
  • The Breakthrough Insight: Because the right array is sorted, if arr1[i] is greater than arr2[j], then every single element to the right of arr2[j] will also be smaller than arr1[i]!
  • Therefore, instead of adding just 1 to our count, we can instantly add all remaining elements in the right array (or calculate the span) in $\mathcal{O}(1)$ time.

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

We can achieve this sorted-array property dynamically across the entire array by leveraging Merge Sort. Merge sort recursively divides the array into halves until single-element arrays remain (which are trivially sorted), and then merges them back together in sorted order.

Execution Trace on [5, 3, 2, 4, 1]

1. Divide Phase (Recursion Tree):

   • Split into [5, 3, 2] and [4, 1]
   • Split [5, 3, 2] into [5, 3] and [2]
   • Split [5, 3] into [5] and [3]

2. Merge & Count Phase (Conquer):

   • Merging [5] and [3]:
     • Compare 5 and 3. 5 > 3, so 5 forms an inversion with 3.
     • Count += 1 (elements remaining in left = mid - low + 1 = 1).
     • Merged result: [3, 5]
   • Merging [3, 5] and [2]:
     • Compare 3 and 2. 3 > 2.
     • Since 3 is greater than 2, all elements from 3 onwards in the left sub-array (3 and 5, totaling 2 elements) are greater than 2.
     • Count += 2.
     • Merged result: [2, 3, 5]
   • Merging [4] and [1]:
     • Compare 4 and 1. 4 > 1.
     • Count += 1.
     • Merged result: [1, 4]
   • Final Merge ([2, 3, 5] and [1, 4]):
     • Compare pointers across both sorted halves, accumulating inversion counts whenever a left element exceeds a right element.

5. Complete Flow Walkthrough (The Merge Step Formula)

When merging two sorted halves:

• Left half boundaries: low to mid
• Right half boundaries: mid + 1 to high

When our pointer in the left half (arr[i]) is greater than our pointer in the right half (arr[j]):

Flow Diagram of Merge & Count

6. Optimal Java Implementation

Here is the clean, production-grade implementation of Count Inversions using Merge Sort without relying on global variables.

import java.util.ArrayList;
import java.util.List;

public class CountInversionsOptimal {

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

    private static long mergeSort(int[] 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 inversions during the merge step across both halves
        count += merge(arr, low, mid, high);
        
        return count;
    }

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

        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp.add(arr[left]);
                left++;
            } else {
                // arr[left] > arr[right] -> Inversion found!
                temp.add(arr[right]);
                // All elements from left to mid are greater than arr[right]
                count += (mid - left + 1);
                right++;
            }
        }

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

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

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

        return count;
    }
}

7. Comparative Synthesis: Brute Force vs. Optimal

8. Real-World Practical Pitfalls & Interview Edge Cases

1. Integer Overflow:

   • The maximum number of inversions in an array of size $N$ is given by $\frac{N(N-1)}{2}$ (in a completely reverse-sorted array). For large $N$ (e.g., $N = 10^5$), this number exceeds the 32-bit integer limit ($\approx 2 \times 10^9$). Always use long for your count variables to prevent arithmetic overflow.

2. Data Mutation Side Effects:

   • Merge sort permanently alters the original array's ordering. In software engineering interviews, explicitly mention this to the interviewer:

     "Note that this optimal algorithm modifies the underlying array. If immutability is required by the calling system, we would need to allocate an auxiliary copy of the array before sorting."

3. Global vs. Local Variables:

   • Avoid using global/static variables for counters in clean production code. Passing and returning long counts recursively ensures thread safety and modularity.

Summary and Key Takeaways

• Definition: An inversion counts pairs (i, j) where i < j and arr[i] > arr[j].
• Brute Force Limit: Nested loops check every pair, resulting in an unacceptable $\mathcal{O}(N^2)$ time complexity for large datasets.
• The Sorted Subarray Advantage: When comparing two sorted sub-arrays, finding one left element greater than a right element allows us to batch-count all remaining elements instantly.
• Divide and Conquer: Merge Sort naturally divides the problem into sorted sub-problems, making it the ideal framework for counting inversions.
• Batch Counting Formula: When arr[left] > arr[right], add (mid - left + 1) directly to the inversion count.
• Time Complexity Optimization: Reduced from $\mathcal{O}(N^2)$ to $\mathcal{O}(N \log N)$ using the merge-sort paradigm.
• Space Complexity: Requires $\mathcal{O}(N)$ auxiliary space for temporary merging arrays.
• Overflow Awareness: Always use 64-bit integers (long) for counting inversions to avoid integer overflow on reverse-sorted arrays.