Count Inversions — Medium Problem & Solution

An inversion is a pair of indices (i, j) with i arr[j] — a pair that is out of order.

Difficulty: Medium
Topics: Arrays, Divide and Conquer, Binary Indexed Tree
Asked at: Amazon, Microsoft, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An inversion is a pair of indices (i, j) with i < j and arr[i] > arr[j] — a pair that is out of order.

The inversion count measures how far an array is from being sorted: a sorted array has 0, and a strictly decreasing array has the maximum possible.

Given arr, return its inversion count.

Example 1

Input: arr = [2,4,1,3,5]
Output: 3
Explanation: The out-of-order pairs are (2,1), (4,1) and (4,3).

Example 2

Input: arr = [2,3,4,5,6]
Output: 0
Explanation: Already sorted.

Example 3

Input: arr = [10,10,10]
Output: 0
Explanation: Equal values are not inversions — the comparison is strict.

Constraints

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

How to solve Count Inversions

Sweep left to right keeping a frequency structure over values already seen. For the current x, the number of earlier values strictly greater than x is seen - (count of values <= x), and a Fenwick tree gives that prefix count in O(log V).

Approach

Create a Fenwick tree over the value range 1 .. 1000, all zeros.
For each element x in order: add seen - query(x) to the answer, where query(x) counts already-inserted values <= x.
Insert x into the tree and increment seen.

Why it works

Every inversion (i, j) is counted exactly once — at the moment j is processed, because arr[i] is already in the tree and arr[i] > arr[j] is exactly what seen - query(arr[j]) measures.

Complexity

Time — O(n log V)
Space — O(V)

Pitfalls

Using query(x) alone counts values <= x, which includes ties; the strict comparison is why the subtraction is from seen.
A Fenwick tree is 1-indexed — a value of 0 would loop forever in the update, so the values here start at 1.

Reference solution

Python

from typing import List

def countInversions(arr: List[int]) -> int:
    MAX = 1001
    bit = [0] * (MAX + 1)

    def add(i: int) -> None:
        while i <= MAX:
            bit[i] += 1
            i += i & -i

    def pref(i: int) -> int:
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    total = 0
    seen = 0
    for x in arr:
        total += seen - pref(x)
        add(x)
        seen += 1
    return total

JavaScript

var countInversions = function(arr) {
    var MAX = 1001;
    var bit = [];
    for (var t = 0; t <= MAX; t++) bit.push(0);
    var total = 0, seen = 0;
    for (var i = 0; i < arr.length; i++) {
        var x = arr[i];
        var s = 0;
        for (var p = x; p > 0; p -= p & -p) s += bit[p];
        total += seen - s;
        for (var q = x; q <= MAX; q += q & -q) bit[q]++;
        seen++;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue