Count Inversion

The problem, simply

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

Count all of them. A sorted array has 0. An array sorted backwards has the most.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look at every pair. For each position i, check every later position j and count the pairs where arr[i] > arr[j].

class Solution {
    public long countInversions(int[] 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: every pair once, about n * n / 2 checks, O(n^2). Extra room: one counter, O(1).

Way 2: the clever way

Use merge sort and count while merging. 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. The first two kinds are counted by the smaller sorts. The third kind is counted during the merge.

1. Split the array in the middle. Count and sort the left half. Count and sort the right half.
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. Every left number from i to the end of the left half is bigger and stood before it. Add that many, mid - i + 1, in one go.

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

    private long sortAndCount(int[] a, int[] tmp, int lo, int hi) {
        if (lo >= hi) return 0;                       // one number has 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;                 // all waiting left numbers are 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 cut in half about log n times, and each level of merging touches every number once, so O(n log n). Extra room: the helper array tmp, O(n), plus O(log n) for the waiting calls.

Watch out for

• The count can be huge. With 100,000 numbers sorted backwards it is about 5 billion, which does not fit in an int. Use long.
• The method sorts the array. Pass a copy if the caller needs the original order.
• Add mid - i + 1, the count of left numbers still waiting, not 1.

What interviewers ask next

• Can you do it another way in O(n log n)? Yes, with a Fenwick tree (a binary indexed tree). Walk from right to left, and for each number ask how many smaller numbers you have already seen, then record this one. Squash big values to ranks first.
• What does the count mean? It is the number of swaps bubble sort makes, and the fewest swaps of neighbours needed to sort the array.
• Count pairs where arr[i] > 2 * arr[j] (reverse pairs). Same merge sort shape, but count with a separate pointer pass before merging, because the merge condition and the count condition differ.
• How similar are two rankings? Relabel one ranking by the other and count inversions. This is the Kendall tau distance.

Remember this

Grown-up words: the messy pairs are inversions, splitting and merging is merge sort (divide and conquer), the pairs with one number in each half are split inversions, and the counting tree from the follow up is a Fenwick tree.