Topics › Arrays › Hard

Inversion of Array (Pre-req: Merge Sort)

Hard TUF ID 2758 SDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an array a of n integers, count its inversions: pairs of indices (i, j) with i < j and a[i] > a[j]. The count measures how far the array is from sorted order: a sorted array has 0 inversions, and a strictly decreasing one has the maximum, n(n-1)/2. Equal values do not form an inversion.

Constraints: 1 ≤ n ≤ 10^5, values fit in an int. The answer can reach about 5 · 10^9, which does not fit in an int, so it is returned as a long. The input array should be left unchanged.

Example 1

a = [5, 3, 2, 4, 1]
answer = 8      // (5,3) (5,2) (5,4) (5,1) (3,2) (3,1) (2,1) (4,1)

Example 2

a = [1, 20, 6, 4, 5]
answer = 5      // (20,6) (20,4) (20,5) (6,4) (6,5)

Example 3

a = [2, 2, 2]
answer = 0      // equal values are not inversions

Approach 1: Brute force

Intuition. The definition talks about pairs, so check every pair i < j and count those that are out of order.

Algorithm.

1. For every i, for every j > i: if a[i] > a[j], increment the count.
2. Return the count.

static long bruteForce(int[] a) {
    long count = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) count++;
        }
    }
    return count;
}

Complexity. Time O(n^2), about 5 · 10^9 comparisons for n = 10^5, far too slow. Space O(1).

We need to count pairs without looking at them one by one, and sorting is the tool for that.

Approach 2: Optimal, count while merge sorting

Intuition. Split the array into a left half and a right half. Every inversion is one of three kinds: both elements in the left half, both in the right half, or one in each (a cross inversion). The first two kinds are the same problem on smaller arrays, so recursion handles them. The question is how to count cross inversions fast.

Here is the key observation: the number of cross inversions does not depend on the order inside each half. A cross pair is “some x from the left half and some y from the right half with x > y”, and rearranging inside a half does not change which such pairs exist. So we may sort both halves first, which is exactly what merge sort’s recursive calls produce, and then count the cross pairs between two sorted lists.

Between two sorted lists, counting is cheap and fits naturally into the merge step. Merging repeatedly compares the front elements L[i] and R[j]:

• If L[i] ≤ R[j], take L[i]. It forms no inversion with R[j] or anything after it.
• If L[i] > R[j], take R[j]. Since the left half is sorted, every remaining left element L[i..mid] is at least L[i], so all of them are greater than R[j]. That is mid - i + 1 cross inversions involving R[j], counted in one step.

Every right element is taken exactly once, and at that moment the remaining left elements are exactly the left elements greater than it. So every cross inversion is counted exactly once.

Algorithm.

1. Copy the array so the input is not modified, and allocate one temporary buffer.
2. mergeSortCount(lo, hi): if the range has fewer than two elements, return 0.
3. Recurse on [lo, mid] and [mid+1, hi] and add their counts.
4. Merge the two sorted halves; whenever the right element is taken, add mid - i + 1.
5. Copy the merged range back and return the total.

static long optimal(int[] a) {
    int[] arr = a.clone();
    return mergeSortCount(arr, new int[arr.length], 0, arr.length - 1);
}

static long mergeSortCount(int[] arr, int[] tmp, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    long count = mergeSortCount(arr, tmp, lo, mid) + mergeSortCount(arr, tmp, mid + 1, hi);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            count += mid - i + 1;                // arr[i..mid] are all greater than arr[j]
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= hi) tmp[k++] = arr[j++];
    for (k = lo; k <= hi; k++) arr[k] = tmp[k];
    return count;
}

Dry run on a = [5, 3, 2, 4, 1]. The left half [5, 3, 2] contributes 3 inversions while being sorted to [2, 3, 5], and the right half [4, 1] contributes 1 while becoming [1, 4]. The final merge counts the cross inversions:

Cross inversions = 4, and the total is 3 + 1 + 4 = 8.

Complexity. Time O(n log n): there are log n levels of recursion, and each level does O(n) merging work; the counting adds only O(1) per step. Space O(n) for the copy and the buffer, plus O(log n) recursion depth.

Edge cases and pitfalls

• <= versus < in the merge. Taking the left element when the two are equal is what keeps equal values from being counted. With <, [2, 2] would report one inversion.
• Overflow. A reversed array of 10^5 elements has 4,999,950,000 inversions. Keep the counter and every partial sum in long; the Java test checks exactly this case.
• Counting mid - i + 1, not 1. Adding one per right element taken counts only one of the larger left elements, which undercounts.
• Modifying the input. Merge sort rearranges the array it works on. Work on a copy unless the caller allows destruction.
• Allocate the buffer once. Creating new arrays in every merge call works but is slower; one shared buffer of size n is enough.
• Empty and single-element arrays. Both have 0 inversions; the base case lo >= hi covers them, including hi = -1 for the empty array.

Related problems

• Count Inversions is the same problem as it appears in the A2Z sheet.
• Reverse Pairs counts pairs with a[i] > 2·a[j] using the same merge-sort skeleton.
• Merge Sorting explains the sort this solution is built on.
• Merge two sorted arrays without extra space practises reasoning about two sorted halves.