Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
An inversion is a pair i < j with a[i] > a[j] — a measure of how unsorted the array is. Counting them naively is O(n²). The trick is to piggyback on merge sort: during the merge step, when you pull an element from the RIGHT half ahead of remaining LEFT-half elements, every one of those remaining left elements forms an inversion with it — add (mid − i + 1) in one shot. Same O(n log n) as the sort itself.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you connect 'count pairs across a split' to merge sort's merge step, see that the left half being sorted lets you count a whole run at once, and avoid the O(n²) double loop.
Where candidates slip
Counting one inversion at a time instead of the whole remaining left run (losing the speedup), using < instead of <= and over-counting equal pairs, or overflowing a 32-bit int on the count.
How to stand out
Decompose the count as left + right + cross, explain why the sorted left half justifies adding (mid − i + 1) in one step, and proactively flag the 64-bit overflow and the <= tie rule.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Divide-and-conquer splits the count into left, right, and cross-inversions; the merge tallies the cross part for free.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Nested Pair Scan
1Hint 1Explore hintHide hint
Translate the definition directly: how many pairs (i, j) with i < j have nums[i] > nums[j]?
2Hint 2Explore hintHide hint
Two nested loops: outer i from 0 to n−1, inner j from i+1 to n−1. Increment a counter whenever nums[i] > nums[j].
3Hint 3Explore hintHide hint
This is correct and obvious but does ~n²/2 comparisons — too slow when n = 10⁵ (≈ 5 × 10⁹ operations).
A · Core idea
The most literal reading of the problem: for every index i, look at every later index j > i and check whether nums[i] > nums[j]. Each time it holds, you've found one inversion, so bump a counter.
Why `j = i + 1`. Inversions are defined on ordered pairs with i < j, so the inner loop must start strictly after i. Starting at i + 1 visits each unordered pair exactly once and never compares an element with itself — the same loop-invariant hygiene as the brute-force pass in Two Sum.
Why the counter must be 64-bit. A strictly descending array of length 10⁵ has n(n−1)/2 ≈ 5 × 10⁹ inversions, which exceeds the ~`2.1 × 10⁹ceiling of a signed 32-bit int. Even the brute force needs along` accumulator, or it silently overflows to a negative number.
Why we don't ship this. The work is quadratic. For n = 10⁵ that's about five billion comparisons — well past any time limit. But stating it first is valuable: it pins down the exact definition (strict >, ordered pairs) and sets up the speedup. The key realization is that the double loop re-derives, from scratch, comparisons that a sorting pass would make anyway — so if we count while sorting, we get the answer almost for free.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [2, 4, 1, 3]Array state
i=1 (4)
4 > 1 and 4 > 3 → two inversions
3C · Code with teaching comments
Reference implementation previewpublic 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]) {Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The brute force checks each pair in isolation, ignoring any structure. Merge sort, by contrast, compares whole sorted runs against each other — so when one element beats another, it beats an entire known block at once. Spotting that 'a sorted half lets me count many pairs in one step' is the whole leap to the optimal solution.
ComplexityO(n²) time, O(1) space — Every ordered pair (i, j) with i < j is checked exactly once → n(n−1)/2 ≈ n²/2 comparisons. No extra space beyond the counter.
E · Edge cases and pitfalls3Using a 32-bit int for the count — overflows on large descending arrays.Explore edge casesHide edge cases
Pitfalls
- Using a 32-bit int for the count — overflows on large descending arrays.
- Starting j at 0 or i — double-counts pairs or compares an element with itself.
- Using >= instead of > — counts equal pairs that aren't inversions.
Approach 2 of 2 · Optimal
Modified Merge Sort (Optimal)
1Hint 1Explore hintHide hint
Split the array in half. Total inversions = inversions fully inside the left half + fully inside the right half + cross-inversions where i is in the left and j is in the right. Recursion handles the first two.
2Hint 2Explore hintHide hint
To count cross-inversions, sort both halves and merge them. When you take an element from the right half before some left-half elements are placed, those left elements are all larger — so they each form an inversion with it.
3Hint 3Explore hintHide hint
Because the left half is sorted, if right[j] < left[i] then right[j] is also less than every left element from i to mid. Add (mid − i + 1) in one step instead of one at a time.
A · Core idea
The whole solution rides on one decomposition. Split the array at mid. Any inversion (i, j) falls into exactly one of three buckets: both indices in the left half, both in the right half, or i in the left and j in the right (a cross-inversion). The recursion counts the first two buckets by solving each half; the merge step counts the third.
Why merging counts cross-inversions cleanly. Suppose both halves are already sorted (they are, by the recursion). Merge them with two pointers, i over the left and j over the right. Compare left[i] and right[j]:
Case A — `left[i] <= right[j]`. The left element is not larger than the right one, so it forms no inversion with right[j] or anything after it. Emit left[i] and advance i. No count.
Case B — `left[i] > right[j]`. Now right[j] is strictly smaller than left[i]. Crucially, because the left half is sorted, every element from left[i] through left[mid] is ≥ left[i] > right[j]. So right[j] is jumping ahead of all of them — that's (mid − i + 1) inversions at once. Add that whole run to the count, emit right[j], and advance j.
That 'add the whole remaining left run in one step' is the entire speedup. The brute force would discover those same (mid − i + 1) pairs one comparison at a time; the sorted-half structure lets the merge book them in O(1).
Why `<=` and not `<` on the tie. Inversions require strict >. When left[i] == right[j], that is not an inversion, so we must take the left element (Case A) and add nothing. Using < would route ties into Case B and over-count. The same <= choice also keeps the sort stable.
Why a 64-bit accumulator. With up to n(n−1)/2 ≈ 5 × 10⁹ inversions for n = 10⁵, the running total exceeds 32-bit int. Java needs long; Python's integers are unbounded so it's a non-issue there, but flag it anyway — it's a favourite interviewer gotcha.
Putting it together. mergeSort(lo, hi) returns the inversion count of nums[lo..hi] and leaves that segment sorted as a side effect. It recurses on [lo, mid] and [mid+1, hi], sums their counts, then adds the cross-count from merging the two now-sorted halves. The top-level call returns the grand total.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [2, 4, 1, 3]Array state
2 vs 1
2 > 1 → take 1; remaining left {2,4} → +2 inversions
3C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The reusable idea is 'augment a classic algorithm with a side computation that costs nothing extra'. Merge sort already walks the cross-boundary comparisons; you just keep a tally. The exact same skeleton — recurse, then count cross-pairs during the merge — solves Reverse Pairs (count i<j with a[i] > 2·a[j]) and Count of Smaller Numbers After Self. Once you see counting as a free passenger on the merge, a whole family of problems opens up.
ComplexityO(n log n) time, O(n) space — Merge sort's recursion tree has depth O(log n), and each level does O(n) merge work — counting cross-inversions adds only O(1) per merge comparison. So the total is the same O(n log n) as the sort. The temporary buffer makes it O(n) space.
E · Edge cases and pitfalls7nums = [1] — Single element → recursion base case returns 0, no merges, 0 inversions.Explore edge casesHide edge cases
Edge cases handled
nums = [1]Single element → recursion base case returns 0, no merges, 0 inversions.nums = [5, 5, 5]All equal; <= routes every tie to the left so no inversions are counted → 0.nums = [1000000000, -1000000000] repeated to length 10⁵Maximal alternating inversions push the count toward ~2.5×10⁹ — confirms the 64-bit accumulator is required.
Pitfalls
- Counting inversions one at a time in the merge instead of adding (mid − i + 1) — loses the O(n log n) speedup.
- Using < instead of <= on the comparison — over-counts equal pairs as inversions.
- Accumulating in a 32-bit int — overflows around 2.1×10⁹ on large inputs.
- Forgetting to copy the merged buffer back — parent merges then operate on unsorted halves and miscount.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long countInversions(int[] nums) { int[] buffer = new int[nums.length]; return mergeSort(nums, buffer, 0, nums.length - 1); } Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Counting one inversion at a time
If you increment by 1 per left element instead of adding the whole remaining run, the merge becomes O(n²) in the worst case and you lose the entire benefit.
Explore the code comparisonHide the code comparison
Counting one inversion at a time
If you increment by 1 per left element instead of adding the whole remaining run, the merge becomes O(n²) in the worst case and you lose the entire benefit.
Don't write this
} else {
buffer[k++] = nums[j++];
for (int t = i; t <= mid; t++) count++; // O(n) extra work per step
}Write this instead
} else {
buffer[k++] = nums[j++];
count += (mid - i + 1); // whole remaining left run at once
}2Strict vs non-strict comparison
Inversions need strict >. Using < on the merge comparison sends ties to the right branch and counts equal pairs as inversions, inflating the result.
Explore the code comparisonHide the code comparison
Strict vs non-strict comparison
Inversions need strict >. Using < on the merge comparison sends ties to the right branch and counts equal pairs as inversions, inflating the result.
Don't write this
if left[i] < right[j]: # WRONG: ties fall to the else branch
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
count += len(left) - iWrite this instead
if left[i] <= right[j]: # ties taken from the left → not counted
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
count += len(left) - i3Integer overflow on the count
For n = 10⁵ the count can reach ~5×10⁹, beyond a signed 32-bit int's ~2.1×10⁹ ceiling, wrapping to a negative number.
Explore the code comparisonHide the code comparison
Integer overflow on the count
For n = 10⁵ the count can reach ~5×10⁹, beyond a signed 32-bit int's ~2.1×10⁹ ceiling, wrapping to a negative number.
Don't write this
int count = 0; // overflows on large descending arraysWrite this instead
long count = 0; // 64-bit accumulatorRevise
Carry the pattern into the interview
Pattern to remember
Modified merge sort — count cross-inversions during merge
Code pattern to memorize
merge(left, right):
while i in left and j in right:
if left[i] <= right[j]: # NO inversion (use <= to skip equals)
take left[i]; i++
else: # left[i] > right[j] → inversion
take right[j]; j++
count += (elements remaining in left)Rules to remember
- 1An inversion is a pair
(i, j)withi < janda[i] > a[j]— strictly greater, so equal values are NOT inversions. - 2Total inversions = inversions inside the left half + inside the right half + cross-inversions counted during the merge. The recursion sums all three.
- 3In the merge, when
right[j] < left[i], every left element fromitomidis also> right[j](the left half is sorted), so addmid − i + 1at once — that's where the speedup comes from. - 4Use
left[i] <= right[j](not<) to take from the left on ties. Using<would count equal pairs as inversions, over-counting. - 5The count can reach
n(n−1)/2 ≈ 5 × 10⁹forn = 10⁵— that overflows 32-bit int. Use a 64-bit accumulator (longin Java).
Use this pattern when
- Count pairs (i, j) with i < j and a[i] > a[j] — or 'how far from sorted is this array?'
- Any 'count cross-pairs across a split' problem that merge sort's partition can absorb
- You need O(n log n), and an O(n²) double loop is too slow
- Variants: reverse pairs (a[i] > 2·a[j]), count smaller-to-the-right, significant inversions
Choose another pattern when
- n is tiny → the O(n²) double loop is simpler and fast enough
- You need the inversions themselves listed, not just the count → enumeration is inherently O(output)
- The comparison isn't a clean order relation → the sorted-half shortcut breaks
- A BIT/Fenwick tree fits your mental model better → it's an equally valid O(n log n) route
Interview takeaway
Counting inversions is the textbook example of folding extra bookkeeping into a classic algorithm for free. Merge sort already compares across the split; you just tally the cross-pairs while merging. The 'add the whole remaining left run at once' move is the insight — it's reused in Reverse Pairs, Count of Smaller Numbers After Self, and any divide-and-conquer cross-pair count.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Divide-and-Conquer Cross-Pair Counting. Trigger on 'count pairs (i, j) with i < j and some order relation between a[i] and a[j]'. Fold the count into merge sort's merge step, adding a whole sorted run at once. Same skeleton powers Reverse Pairs and Count of Smaller Numbers After Self; a Fenwick/BIT is the alternative O(n log n) route.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Reverse PairsComing soonCount i < j with nums[i] > 2·nums[j] — same merge-sort skeleton, separate counting pass before merging.
- Count of Smaller Numbers After SelfComing soonPer-element counts of smaller elements to the right via merge sort on (value, index) pairs or a BIT.
- Kth Largest Element via QuickselectAnother divide-and-conquer order-statistic problem reusing the partition primitive.
- Merge Sort (tutorial)Coming soonThe base algorithm this augments — understand the merge step cold first.