Find the inversion count

The problem, simply

You get an array of numbers. A pair of positions i < j is out of order when arr[i] > arr[j]: a bigger number stands before a smaller one. Each such pair is an inversion.

Count them all. A sorted array has 0. An array sorted backwards has the most, n * (n - 1) / 2. The count tells you how far the array is from sorted.

A story to remember it

Picture it

Examples

Way 1: the simple way

Check every pair. For each i, look at every later j and count when arr[i] > arr[j].

class Solution {
    public long inversionCount(long[] arr) {
        long count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) count++;   // bigger one stands first
            }
        }
        return count;
    }
}

How long it takes: about n * n / 2 pair checks, O(n^2). With half a million numbers that is over a hundred billion checks. Extra room: O(1).

Way 2: the clever way

Every out of order pair is one of three kinds: both numbers in the left half, both in the right half, or one in each half. Merge sort already splits the array this way. So:

1. Split in the middle. Count (and sort) the left half. Count (and sort) the right half. The smaller sorts do this by splitting again.
2. Merge the two sorted halves with fingers i (left) and j (right).
3. If left[i] <= right[j], the left number goes down first. No new pairs.
4. If right[j] is smaller, it goes down first, and every left number from i to the end of the left half is bigger and stood before it. Add mid - i + 1 at once.

The tree shows the pieces. Each piece's note says how many pairs its merge found.

class Solution {
    public long inversionCount(long[] arr) {
        if (arr.length < 2) return 0;
        return sortAndCount(arr, new long[arr.length], 0, arr.length - 1);
    }

    private long sortAndCount(long[] a, long[] tmp, int lo, int hi) {
        if (lo >= hi) return 0;                      // one number, no pairs
        int mid = lo + (hi - lo) / 2;
        long count = sortAndCount(a, tmp, lo, mid);  // pairs inside the left half
        count += sortAndCount(a, tmp, mid + 1, hi);  // pairs inside the right half
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];                   // left goes first, no new pairs
            } else {
                count += mid - i + 1;                // every waiting left number is bigger
                tmp[k++] = a[j++];
            }
        }
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= hi) tmp[k++] = a[j++];
        for (k = lo; k <= hi; k++) a[k] = tmp[k];
        return count;
    }
}

How long it takes: the array is halved about log n times, and each level of merging touches every number once: O(n log n). Extra room: the helper array, O(n), plus O(log n) for waiting calls.

Watch out for

• The count can reach about n^2 / 2, over a hundred billion for half a million numbers. Use long for the count.
• The values themselves can be huge on GeeksforGeeks (up to 10^18), so store them in long[].
• Add mid - i + 1 (all waiting left numbers), not 1.
• The method sorts the input. Copy it first if the caller needs the original order.

What interviewers ask next

• Another O(n log n) way? A Fenwick tree (binary indexed tree): walk from right to left, ask how many smaller numbers you have already seen, then add this one. Squash big values into ranks first.
• What does the count mean? It equals the number of swaps bubble sort or insertion sort makes, and the fewest swaps of neighbours needed to sort the array.
• Count pairs with arr[i] > 2 * arr[j] (LeetCode 493, reverse pairs). Same merge sort, but count with a separate finger pass before the merge, since the count rule and the merge rule differ.
• For each number, how many smaller numbers are on its right (LeetCode 315)? Same merge, but track original positions and add the count to each left number as it goes down.
• How similar are two rankings? Relabel one ranking by the other and count inversions. That is the Kendall tau distance.

Remember this

Grown-up words: an out of order pair is an inversion, splitting and merging is merge sort (divide and conquer), pairs across the two halves are split inversions, and the helper array is the auxiliary buffer.