Problem 14.6 · Sorting and Divide & ConquerHard

Count Inversions

What it teaches: Piggyback on merge sort: when an element from the right half is merged first, it forms an inversion with every element left in the left half.

The problem

An inversion is a pair (i, j) with i < j and nums[i] > nums[j]. Return the number of inversions in nums.

Example 1

Input: nums = [2, 4, 1, 3, 5]
Output: 3

(2,1), (4,1), (4,3).

Example 2

Input: nums = [5, 4, 3, 2, 1]
Output: 10

Constraints

1 ≤ n ≤ 10⁵
Answer fits in a long

Pattern clues in the wording

→ Count pairs out of order
→ n up to 10⁵: O(n²) too slow

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public long countInversions(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [2,4,1,3,5]	3
2	nums = [5,4,3,2,1]	10
3	nums = [1,1,1]	0

From slow to fast

Approaches

1. Brute force · O(n²)2. Optimal: merge sort with counting · O(n log n)

Brute force

Time O(n²) Space O(1)

Check every pair.

Approach 1

class Solution {
    public long countInversions(int[] nums) {
        long count = 0;
        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length; j++)
                if (nums[i] > nums[j]) count++;
        return count;
    }
}

Verdict: 5 × 10⁹ pairs at the limit: too slow.

Optimal: merge sort with counting

Time O(n log n) Space O(n)

Merge as usual. When taking right[j] while left[i..mid] remain, add (mid − i + 1): all those remaining left elements are larger than right[j] and come before it.

Approach 2

class Solution {
    public long countInversions(int[] nums) {
        int[] a = nums.clone();
        return sort(a, new int[a.length], 0, a.length - 1);
    }

    private long sort(int[] a, int[] tmp, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = (lo + hi) >>> 1;
        long count = sort(a, tmp, lo, mid) + sort(a, tmp, mid + 1, hi);
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else {
                count += mid - i + 1;          // a[i..mid] are all > a[j]
                tmp[k++] = a[j++];
            }
        }
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= hi) tmp[k++] = a[j++];
        System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
        return count;
    }
}

Verdict: The classic divide-and-conquer counting trick.

Before you submit

Edge cases and common mistakes

Test these inputs

Sorted → 0
Reverse sorted → n(n − 1)/2
Duplicates (equal values aren't inversions)

Mistakes people make

Using < instead of <= in the merge (counts equal pairs).
Counting in an int (overflows for n = 10⁵).

Interview

Follow-up questions

How else could you count them?

Command Palette