You are given an array of integers arr. Your task is to count the number of inversions in it.
An inversion is a pair of indices (i, j) such that i < j but arr[i] > arr[j] — a pair of elements that stand in the wrong order compared to the sorted array.
Return the total number of inversions. A fully sorted (non-decreasing) array has 0 inversions; a reverse-sorted array has the maximum possible, n * (n - 1) / 2.
Think of the answer as the array's messiness score — the exact number of adjacent swaps a bubble sort would need to fix it.
arr[i] > arr[j], which is why [10, 10, 10] has zero inversions. In the merge step this means ties must go to the left half (left[i] <= right[j]) — using strict < there silently counts equal pairs.n * (n - 1) / 2 for a reverse-sorted array — about 5 * 10^9 when n = 10^5. Accumulate the count in a 64-bit-wide type when constraints push into that territory.10^4 no coordinate compression is even needed. Also O(n log n), and it generalizes to online updates.len(left) - i jumps to the individual right elements — this is Count of Smaller Numbers After Self, the per-element version of this exact technique.Input: arr = [2, 4, 1, 3, 5] Output: 3 Three pairs are out of order: (2, 1), (4, 1) and (4, 3).
Input: arr = [2, 3, 4, 5, 6] Output: 0 The array is already sorted, so no pair is out of order.
Input: arr = [10, 10, 10] Output: 0 Equal elements are never an inversion — the comparison is strictly greater-than.
- 1 <= arr.size <= 10^5 - 1 <= arr[i] <= 10^4
Counting inversions looks like a simple pair-counting exercise, but it hides one of the most elegant tricks in algorithm design: making a sorting algorithm count while it sorts. The arc here — brute-force pair check, then merge sort with a counter — is a divide-and-conquer pattern you will reuse again and again.
O(n^2) motivates everything else.In plain English: for every pair of positions where the earlier element is strictly bigger than the later one, add one to the count.
Formally: count the pairs (i, j) with i < j and arr[i] > arr[j].
Worked example — arr = [2, 4, 1, 3, 5]
index: 0 1 2 3 4 value: 2 4 1 3 5 (2, 1): arr[0]=2 > arr[2]=1 ✓ (4, 1): arr[1]=4 > arr[2]=1 ✓ (4, 3): arr[1]=4 > arr[3]=3 ✓ answer: 3
[2, 3, 4, 5, 6] is sorted → 0 inversions. [10, 10, 10] has equal elements only — the comparison is strict, so also 0.
Asking two or three sharp questions before coding tells the interviewer you think about contracts, not just code.
“Can the array contain duplicate values, and do equal elements count as an inversion?”
Duplicates are allowed, and equal elements are never an inversion — the condition is strictly greater-than. This decides whether your merge step ties break to the left half.
“Are the values bounded?”
Here values fit in a small range, which even unlocks a Fenwick-tree alternative; the merge sort solution works for any comparable values.
“What should a single-element or already-sorted array return?”
Zero — no pair exists, or no pair is out of order. Good smoke tests for the recursion base case.
“What is the answer for a reverse-sorted array?”
Every pair is inverted: n * (n - 1) / 2. This is the maximum and a great sanity check.
“How large can the array be?”
Up to 10^5 elements. Checking all ~5 * 10^9 pairs is far too slow — we need O(n log n), which is exactly what pointing at merge sort signals.
“Can the count itself get large?”
Up to n * (n - 1) / 2 — accumulate it in a type wide enough for the constraints so the counter never overflows.
Before I start, I have a few clarifying questions.
First — do equal elements count as an inversion, or is the comparison strictly greater-than?
Second — with n up to ten to the fifth, an all-pairs check is about five billion operations, so I will aim for an n log n approach.
And finally — I will sanity-check with a sorted array, which should give zero, and a reverse-sorted one, which should give n times n minus one over two.
The inversion count equals the number of adjacent swaps bubble sort needs to sort the array. Sorted → 0; reverse-sorted → n * (n - 1) / 2. So this problem is secretly asking: how unsorted is this array? That reframing is the hint that a sorting algorithm might count the answer as a side effect.
Cut the array in half. Every inversion pair (i, j) lives entirely in the left half, entirely in the right half, or straddles the cut (i on the left, j on the right). The first two groups are the same problem on smaller arrays — recursion handles them. Only the cross pairs need new work.
[ 2 4 | 1 3 5 ] left right cross pairs: (2,1), (4,1), (4,3)
While merging two sorted halves, the moment right[j] is placed before left[i], that right element is smaller than left[i] and every element still waiting after it — all of them sorted, all of them bigger. So one placement counts len(left) - i inversions in a single O(1) step. Sorting the halves does not destroy the answer — we already counted their internal inversions recursively before rearranging them.
left = [2, 4] right = [1, 3, 5] take 1 → jumps ahead of [2, 4] → +2 inversions take 2 take 3 → jumps ahead of [4] → +1 inversion take 4, take 5 total: 3 ✓
| Brute force (all pairs) | Optimal (merge sort count) | |
|---|---|---|
| Time | O(n²) | O(n log n) |
| Space | O(1) | O(n) |
| n = 10^5 | ~5 × 10^9 checks — far too slow | ~1.7 × 10^6 steps — instant |
Both are implemented in full, in all four languages, in the Approaches selector below.
Key takeaway
Divide and conquer can count while it sorts: split the pairs into left, right, and cross groups, recurse on the halves, and harvest all cross inversions in linear time during the merge — because a right element placed early jumps ahead of every remaining left element at once. The same skeleton solves Reverse Pairs and Count of Smaller Numbers After Self.
sort_count(a):
if len(a) <= 1: return a, 0
left, x = sort_count(first half)
right, y = sort_count(second half)
merge left and right; whenever right[j] wins,
add (len(left) - i) to z
return merged, x + y + z