Find the inversion count

Problem Statement

Given an array of N integers, count the number of inversions. An inversion occurs when a larger element appears before a smaller element, i.e., for indices i < j, if arr[i] > arr[j], then (i, j) is an inversion.

Constraints:

• 1 ≤ N ≤ 10^5
• 1 ≤ arr[i] ≤ 10^9

Example:

• Input: arr = [2, 4, 1, 3, 5]
• Output: 3
• Explanation: Inversions are (2,1), (4,1), (4,3) → indices (0,2), (1,2), (1,3)

Example 2:

• Input: arr = [5, 4, 3, 2, 1]
• Output: 10
• Explanation: Every pair (i,j) where i < j is an inversion = C(5,2) = 10

Approach 1: Brute Force (Nested Loops)

Intuition

Check every pair (i, j) where i < j and count pairs where arr[i] > arr[j].

Algorithm

1. Use two nested loops
2. For each pair (i, j) where i < j
3. If arr[i] > arr[j], increment count

public class Solution {
    public long countInversionsBrute(int[] arr) {
        int n = arr.length;
        long count = 0;
        
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Checking all pairs
• Space Complexity: O(1) - No extra space

Approach 2: Merge Sort Based (Optimal)

Intuition

During merge sort, when merging two sorted halves, if an element from the right half is placed before an element from the left half, it creates inversions with all remaining elements in the left half.

Key Insight: When merging [left] and [right]:

• If left[i] > right[j], then left[i], left[i+1], ..., left[mid] all form inversions with right[j]
• Count = mid - i + 1 (number of remaining elements in left)

Algorithm

1. Divide array into two halves
2. Recursively count inversions in each half
3. Count split inversions during merge
4. Total = left inversions + right inversions + split inversions

public class InversionCount {
    private long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;
        long invCount = 0;
        
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                invCount += (mid - i + 1);
                temp[k++] = arr[j++];
            }
        }
        
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        
        for (int idx = left; idx <= right; idx++) {
            arr[idx] = temp[idx];
        }
        
        return invCount;
    }
    
    private long mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
        long invCount = 0;
        
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            invCount += mergeSortAndCount(arr, temp, left, mid);
            invCount += mergeSortAndCount(arr, temp, mid + 1, right);
            invCount += mergeAndCount(arr, temp, left, mid, right);
        }
        
        return invCount;
    }
    
    public long countInversions(int[] arr) {
        int n = arr.length;
        int[] temp = new int[n];
        return mergeSortAndCount(arr, temp, 0, n - 1);
    }
    
    public static void main(String[] args) {
        InversionCount ic = new InversionCount();
        int[] arr = {2, 4, 1, 3, 5};
        System.out.println(ic.countInversions(arr));  // Output: 3
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Same as merge sort
• Space Complexity: O(n) - For temporary array

Alternative: Using Fenwick Tree (BIT)

For online queries or when array is modified:

Key Takeaways

1. Merge Sort Insight: Inversions are counted during the merge step
2. Split Inversions: When right element is smaller, it forms inversions with all remaining left elements
3. Stable Sort: Merge sort preserves relative order of equal elements
4. Divide and Conquer: Total = left + right + split inversions
5. Sortedness Metric: Inversion count measures how far array is from sorted
6. Maximum Inversions: For reverse sorted array: n(n-1)/2
7. Applications: Collaborative filtering, ranking, measuring sortedness