☕ DSA Java Articles

Topics › Arrays › Hard

Count Inversions

Hard TUF ID 20 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an integer array nums. An inversion is a pair of indices (i, j) with i < j and nums[i] > nums[j]: a pair of elements that are in the wrong order relative to a sorted array. Return the total number of inversions. Equal elements do not form an inversion.

Constraints: 0 ≤ n ≤ 10^5, values fit in a 32-bit signed integer. The answer can be as large as n(n-1)/2 ≈ 5 × 10^9, so return a long.

Example 1

nums = [5, 3, 2, 4, 1]
answer = 8

The inverted pairs are (5,3) (5,2) (5,4) (5,1) (3,2) (3,1) (2,1) (4,1).

Example 2

nums = [1, 2, 3, 4, 5]
answer = 0

The array is sorted, so no pair is out of order. The reverse, [5, 4, 3, 2, 1], has every pair inverted: 10.

Approach 1: Brute force

Intuition. The definition is a statement about pairs, so check every pair i < j and count those with nums[i] > nums[j].

Algorithm.

  1. For every i, for every j > i: if nums[i] > nums[j], increment the count.
  2. Return the count.
static long bruteForce(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;
}

Complexity. Time O(n^2). Space O(1).

For n = 10^5 that is 5 × 10^9 comparisons: too slow. Note that we need the count, not the pairs themselves, which is the opening for a divide-and-conquer approach.

Approach 2: Optimal, merge sort with counting

Intuition. Split the array in half. Every inversion is one of three kinds: both indices in the left half, both in the right half, or i in the left and j in the right. The first two kinds are the same problem on smaller arrays, so recursion handles them. The cross pairs are the interesting part, and here sorting helps: if both halves are sorted, the cross inversions can be counted during the merge.

During a merge, when the next element to emit comes from the right half (a[j]) because it is smaller than the current left element a[i], then a[j] is also smaller than every remaining left element a[i], a[i+1], ..., a[mid] (the left half is sorted). All of those are to the left of a[j] in the original array, so each forms an inversion with it: add mid - i + 1 in one step. When the left element is emitted instead (a[i] <= a[j]), it forms no inversion with a[j] or any later right element, so nothing is added.

Sorting as we go is not a side effect to be tolerated; it is what makes the counting constant-time per emitted element. We operate on a copy so the caller’s array is preserved.

Algorithm.

  1. If the range has fewer than two elements, return 0.
  2. Recursively count inversions in a[lo .. mid] and a[mid+1 .. hi]; both halves come back sorted.
  3. Merge: when taking a[j] from the right because a[i] > a[j], add mid - i + 1 to the count.
  4. Copy the merged range back and return the total.
static long optimal(int[] nums) {
    int[] a = nums.clone();                                  // sorting happens on a copy
    return mergeSortCount(a, new int[a.length], 0, a.length - 1);
}

static long mergeSortCount(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    long count = mergeSortCount(a, tmp, lo, mid) + mergeSortCount(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;
}

Dry run on [5, 3, 2, 4, 1]. The recursion splits into [5, 3, 2] and [4, 1].

i points to j points to emit added running cross count
2 1 1 (right) 3 3
2 4 2 (left) 0 3
3 4 3 (left) 0 3
5 4 4 (right) 1 4
5 done 5 0 4

Total 3 + 1 + 4 = 8.

Complexity. Time O(n log n): the recursion has log n levels, each doing O(n) work in merges. Space O(n) for the shared buffer tmp plus O(log n) recursion stack.

The comparison must be a[i] <= a[j] to send equal elements left first; using < would count equal pairs as inversions, and [3, 3, 3] would return 3 instead of 0.

Approach 3: Optimal alternative, Fenwick tree over ranks

Intuition. Reformulate: the number of inversions is the sum over i of “how many elements to the right of i are smaller than nums[i]”. Scan from right to left and keep a multiset of the values already seen; for each new element ask how many stored values are strictly smaller, then insert it. A Fenwick tree (binary indexed tree) answers prefix counts and does point updates in O(log n) each. Values can be huge or negative, so first replace each value by its rank, the number of distinct positions in the sorted array holding smaller values; equal values share a rank, which is exactly what makes the “strictly smaller” query exclude them.

Algorithm.

  1. Sort a copy to get ranks; rank(v) = lowerBound(sorted, v).
  2. Scan i from n - 1 down to 0:
    • Query the tree for the count of stored positions ≤ rank(nums[i]); these are the already seen (to the right) values strictly smaller. Add to the answer.
    • Insert nums[i] at position rank + 1 (Fenwick trees are 1-based).
static long optimalFenwick(int[] nums) {
    int n = nums.length;
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int[] tree = new int[n + 1];                             // 1-based Fenwick tree over ranks
    long count = 0;
    for (int i = n - 1; i >= 0; i--) {
        int rank = lowerBound(sorted, nums[i]);              // number of distinct positions holding values < nums[i]
        for (int idx = rank; idx > 0; idx -= idx & -idx) count += tree[idx];   // elements to the right that are smaller
        for (int idx = rank + 1; idx <= n; idx += idx & -idx) tree[idx]++;     // record nums[i] at position rank + 1
    }
    return count;
}

static int lowerBound(int[] sorted, int v) {
    int lo = 0, hi = sorted.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (sorted[mid] < v) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Complexity. Time O(n log n): a sort, then n iterations each with a binary search and two O(log n) tree walks. Space O(n) for the sorted copy and the tree.

Why does querying prefix rank exclude equal values? An element w is stored at position rank(w) + 1. It is counted when rank(w) + 1 ≤ rank(v), that is rank(w) < rank(v), which holds exactly when w < v. Equal values have equal ranks and are left out, as required.

The merge-sort method is the one interviewers expect and is slightly faster in practice. The Fenwick version is worth knowing because it adapts easily to variants such as counting pairs with nums[i] > 2 * nums[j] or “smaller elements to the right” per index.

Edge cases and pitfalls