GeeksforGeeks Hard

Count Inversions

Count pairs (i, j) with i < j but nums[i] > nums[j] — how far the array is from sorted.

arraymerge-sortdivide-and-conquer

02

Intuition

💡

During a merge of two sorted halves, the moment you take an element from the right half before elements remain in the left half, that right element is smaller than all remaining left elements — that's a whole batch of inversions counted in one step.

03

Approach

1

Recurse on halves

Inversions = inversions inside left + inside right + cross inversions. The first two come from recursion.

2

Count during merge

Merging sorted halves: when right[j] < left[i], it jumps ahead of len(left) − i left elements — add that many inversions at once.

3

Why it's fast

Each merge is linear and there are log n levels → O(n log n), versus O(n²) brute force.

04

Solution & live demo

python

▶1def count_inversions(nums):
▶2    def sort(a):
▶3        if len(a) <= 1: return a, 0
▶4        mid = len(a) // 2
▶5        left, x = sort(a[:mid])
▶6        right, y = sort(a[mid:])
▶7        merged, inv, i, j = [], x + y, 0, 0
▶8        while i < len(left) and j < len(right):
▶9            if left[i] <= right[j]:
▶10                merged.append(left[i]); i += 1
▶11            else:
▶12                inv += len(left) - i   # right[j] beats all remaining left
▶13                merged.append(right[j]); j += 1
▶14        merged += left[i:] + right[j:]
▶15        return merged, inv
▶16    return sort(nums)[1]

05

Edge cases

Already sorted

Right elements never jump ahead → 0 inversions.

Reverse sorted

Every pair inverts: n(n−1)/2, counted in batches.

06

Complexity

Time

O(n log n)

Space

O(n)

Standard merge sort with a counter.