Count Inversions

Problem Statement

Given an array arr[], count the number of inversions in the array. Two elements arr[i] and arr[j] form an inversion if i < j and arr[i] > arr[j].

Example: Input: arr = [8, 4, 2, 1]
Output: 6
Explanation: Inversions are (8,4), (8,2), (8,1), (4,2), (4,1), (2,1).

Approach 1: Brute Force

Explanation: Use two nested loops to check every pair of elements and count inversions where i < j and arr[i] > arr[j].

Time Complexity: O(n2)

Space Complexity: O(1)

function countInversions(arr):
    n = length(arr)
    count = 0
    
    for i = 0 to n-2:
        for j = i+1 to n-1:
            if arr[i] > arr[j]:
                count = count + 1
    
    return count

Approach 2: Optimized Brute Force with Early Termination

Explanation: Similar to brute force but with minor optimizations like reducing redundant comparisons. Though still O(n²), it performs better in practice by avoiding unnecessary iterations when possible.

Time Complexity: O(n2)

Space Complexity: O(1)

function countInversions(arr):
    n = length(arr)
    count = 0
    
    for i = 0 to n-2:
        // Early termination: if current element is smallest, 
        // no inversions possible
        if arr[i] <= min(arr[i+1] to arr[n-1]):
            continue
            
        for j = i+1 to n-1:
            if arr[i] > arr[j]:
                count = count + 1
    
    return count

Approach 3: Divide and Conquer (Modified Merge Sort)

Explanation: Divide the array into two halves. Count inversions in left half, right half, and cross inversions during merge. When merging, if an element from the right half is smaller than an element from the left half, all remaining elements in the left half form inversions with it.

Time Complexity: O(n log n)

Space Complexity: O(n) for temporary array

function mergeAndCount(arr, temp, left, mid, right):
    i = left
    j = mid + 1
    k = left
    invCount = 0
    
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i = i + 1
        else:
            temp[k] = arr[j]
            invCount = invCount + (mid - i + 1)
            j = j + 1
        k = k + 1
    
    while i <= mid:
        temp[k] = arr[i]
        i = i + 1
        k = k + 1
    
    while j <= right:
        temp[k] = arr[j]
        j = j + 1
        k = k + 1
    
    for i = left to right:
        arr[i] = temp[i]
    
    return invCount

function mergeSortAndCount(arr, temp, left, right):
    invCount = 0
    if left < right:
        mid = (left + right) / 2
        
        invCount = invCount + mergeSortAndCount(arr, temp, left, mid)
        invCount = invCount + mergeSortAndCount(arr, temp, mid+1, right)
        invCount = invCount + mergeAndCount(arr, temp, left, mid, right)
    
    return invCount

    function countInversions(arr):
    n = length(arr)
    temp = new array of size n
    return mergeSortAndCount(arr, temp, 0, n-1)

The Divide and Conquer approach using Modified Merge Sort is the most commonly used optimal solution for counting inversions with O(n log n) time complexity. It elegantly combines sorting with inversion counting.


Flowchart