Google — Count Inversions (Modified Merge Sort)

Problem Statement#

Given an array, count the number of inversions — pairs (i, j) such that i < j and arr[i] > arr[j]. This equals the number of swaps required to sort the array using adjacent swaps (bubble sort).

Constraints:

• 1 <= arr.length <= 5 * 10^4
• -10^9 <= arr[i] <= 10^9
• Answer fits in a 64-bit integer

Input:  arr = [2, 4, 1, 3, 5]
Output: 3  (pairs: (2,1), (4,1), (4,3))

Input:  arr = [5, 4, 3, 2, 1]
Output: 10  (all pairs form inversions)

Why This Problem Matters#

Count Inversions is a Google interview problem (LeetCode 315 asks related Count of Smaller Numbers After Self) that appears frequently in Google and Jane Street phone screens. It tests a fundamental divide-and-conquer skill: the ability to count cross-partition relationships during merge sort without extra passes. This "piggyback on merge" technique appears in many advanced algorithms.

The brute force checks every pair — O(N^2) — which is too slow for arrays of length 50,000. Modified merge sort solves it in O(N log N) by counting inversions between the left and right halves during the merge step. This is the same time complexity as sorting itself, and it is elegant: sorting the array and counting inversions happen simultaneously.

Google also asks this in the context of "number of swaps to sort" or "how far is this permutation from sorted?" — all equivalent to the inversion count. Amazon uses it in warehouse distance optimization and ranking systems.

The Core Insight#

During merge sort, when merging left and right sorted halves, if right[j] < left[i], then right[j] is smaller than ALL remaining elements in the left half (since left is sorted). This gives exactly len(left) - i inversions at once. This is the key piggyback: count cross-inversions for free during the merge.

Total inversions = inversions within left half + inversions within right half + cross-inversions counted during merge.

Visual Dry Run#

arr = [2, 4, 1, 3]

Solution (Optimal)#

class Solution:
    def countInversions(self, arr: list) -> int:
        def merge_sort(arr):
            if len(arr) <= 1:
                return arr, 0
 
            mid = len(arr) // 2
            left, left_inv = merge_sort(arr[:mid])
            right, right_inv = merge_sort(arr[mid:])
 
            merged = []
            inversions = left_inv + right_inv
            i = j = 0
 
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    merged.append(left[i])
                    i += 1
                else:
                    # left[i] > right[j]: all remaining left elements form inversions with right[j]
                    inversions += len(left) - i
                    merged.append(right[j])
                    j += 1
 
            merged.extend(left[i:])
            merged.extend(right[j:])
            return merged, inversions
 
        _, total = merge_sort(arr)
        return total

function countInversions(arr) {
    function mergeSort(arr) {
        if (arr.length <= 1) return [arr, 0];
 
        const mid = Math.floor(arr.length / 2);
        const [left, leftInv] = mergeSort(arr.slice(0, mid));
        const [right, rightInv] = mergeSort(arr.slice(mid));
 
        const merged = [];
        let inversions = leftInv + rightInv;
        let i = 0, j = 0;
 
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                merged.push(left[i++]);
            } else {
                inversions += left.length - i;
                merged.push(right[j++]);
            }
        }
 
        return [[...merged, ...left.slice(i), ...right.slice(j)], inversions];
    }
 
    return mergeSort(arr)[1];
}

Time: O(N log N) — same recurrence as merge sort Space: O(N) — temporary arrays during merge; O(log N) call stack

Common Mistakes#

• Counting inversions as len(right) - j instead of len(left) - i — wrong pointer
• Not accumulating left and right inversions before cross-inversions — misses recursive counts
• Using left[i] < right[j] instead of <= — causes double-counting equal elements
• Modifying the original array in-place without tracking count — loses the inversion signal
• Integer overflow: use 64-bit integers when the answer can be N*(N-1)/2 = O(N^2)

Interview Tips#

• Explain the key insight before coding: "When right[j] < left[i], all remaining left elements invert with right[j]"
• Trace through the merge step for [4,2] vs [1,3] before coding — shows the insight clearly
• Mention the output is also sorted — you get sorting for free alongside the count
• Note the answer can be O(N^2) in magnitude — use int64 / Python's big integers
• Google sometimes asks for the actual list of inversions — return pairs from the merge step

Follow-up Questions#

• How do you count inversions in a nearly-sorted array? — Merge sort still O(N log N); no better general algorithm
• How do you find the minimum swaps to sort? — Same as inversion count for adjacent swaps
• What if elements are not distinct? — Use <= in the comparison to avoid double-counting
• How does this relate to BIT/Fenwick tree approach? — BIT achieves O(N log N) via coordinate compression + prefix sums
• What is the maximum possible inversion count for N elements? — N*(N-1)/2 when array is reverse sorted

Key Takeaways#

• Inversions are pairs (i,j) with i < j and arr[i] > arr[j] — equivalent to adjacent swap distance from sorted order
• The merge sort approach counts cross-inversions in O(N) during each merge: when left[i] > right[j], add len(left)-i
• Total inversions = left half inversions + right half inversions + cross-inversions (divide and conquer)
• Time is O(N log N) — the inversion count piggybacks on merge sort with no extra asymptotic cost
• Google tests this to verify divide-and-conquer thinking beyond simple recursion
• The answer can reach N*(N-1)/2 ≈ N^2/2, so use 64-bit integers to avoid overflow
• An alternative O(N log N) approach uses a Binary Indexed Tree (Fenwick tree) with coordinate compression