Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
An inversion is a pair (i, j) with i < j but arr[i] > arr[j] — the number of adjacent swaps a bubble/insertion sort would perform. Counting them naively is O(n²). The trick: piggyback on merge sort. During the merge of two sorted halves, when you take an element from the RIGHT half before the left half is exhausted, every remaining left element is greater than it, so add `len(left) - i` to the count. Total O(n log n). Use a 64-bit integer (long) — the count can reach ~n²/2 ≈ 5·10⁹.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can augment merge sort to count cross-half inversions in O(n log n), get the `len(left) - i` increment exactly right, and remember that the count needs 64 bits.
Where candidates slip
Adding 1 instead of `len(left) - i` (counts only adjacent inversions), using 32-bit int and overflowing, or counting equal elements as inversions by using `<` instead of `<=`.
How to stand out
Derive the `len(left) - i` jump from the sortedness invariant, state the long-overflow risk up front, and note insertion-sort swap count equals the inversion count.
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: count within each half plus inversions that cross the split.
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 — Count All Pairs
1Hint 1Explore hintHide hint
An inversion is literally a pair (i, j), i < j, with arr[i] > arr[j]. What is the most direct way to count those?
2Hint 2Explore hintHide hint
Two nested loops: for each i, count later indices j with arr[i] > arr[j].
3Hint 3Explore hintHide hint
This is correct and trivial but O(n²) — fine for n ≤ a few thousand, far too slow at n = 10⁵.
A · Core idea
Directly count every out-of-order pair. For each index i, scan all later indices j > i and increment a counter whenever arr[i] > arr[j].
Why it is the right definition-check. It is the literal restatement of the problem, so it's the correct reference implementation to validate the fast version against on small inputs.
Why it fails the constraints. With n = 10⁵, the quadratic pair count is ~`5·10⁹— that's also why the answer needslong. The same magnitude that breaks intstorage breaks the brute-force *time* budget, which is the clue that anO(n log n)` method is expected.
Note on the counter type. Even the brute force must accumulate into a long; the number of inversions is identical regardless of method, and it can exceed 2³¹−1.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [2, 1, 3, 1, 2]Array state
i=0
2 > 1, 2 > 1 → +2
4C · Code with teaching comments
Reference implementation previewpublic long countInversions(int[] arr) { long count = 0; for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) count++;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 quadratic cost comes from re-comparing pairs that a sort would compare anyway. If we could count out-of-order pairs while sorting, we'd reuse that work — which is exactly what merge sort enables.
ComplexityO(n²) time, O(1) space — n(n−1)/2 pair checks ≈ n²/2 comparisons; for n = 10⁵ that is ~5·10⁹ operations, well beyond a 1–2 second budget.
E · Edge cases and pitfalls4arr = [1, 1, 1] — No strict inversions → 0; verifies equals are excluded.Explore edge casesHide edge cases
Edge cases handled
arr = [1, 1, 1]No strict inversions → 0; verifies equals are excluded.
Pitfalls
- Using int for the counter — overflows for large n.
- Using >= and counting equal elements as inversions.
- Quadratic time — times out at n = 10⁵.
Approach 2 of 2 · Optimal
Merge Sort with Inversion Counting (Optimal)
1Hint 1Explore hintHide hint
Merge sort splits the array and merges sorted halves. While merging, both halves are already sorted — what does that tell you when a right-half element is smaller than a left-half element?
2Hint 2Explore hintHide hint
If you ever take right[j] while left still has elements from index i onward, then ALL of left[i..] are greater than right[j] — that's `len(left) - i` inversions at once.
3Hint 3Explore hintHide hint
Total inversions = inversions(left) + inversions(right) + cross inversions counted during the merge. Use long; take from the left on ties (left[i] <= right[j]) so equals aren't counted.
A · Core idea
Run a standard merge sort, but augment the merge so it counts inversions for free.
The key invariant. When we merge two halves, both are already sorted. We walk a pointer i over left and j over right, always emitting the smaller front element. If left[i] <= right[j] we emit left[i] — no inversion, because left[i] originally came before everything in right. But if left[i] > right[j], we emit right[j]; since left is sorted, every remaining element left[i], left[i+1], …, left[len-1] is also greater than right[j], and each of those originally sat to the left of right[j]. That's exactly len(left) - i inversions, added in one shot.
Why this captures every inversion exactly once. Any inversion (p, q) has p left of q. Either both indices fall in the same half (counted by that half's recursive call) or they straddle the split (counted during this merge, when right[j] is emitted ahead of the still-pending left[i]). The three buckets — left, right, cross — are disjoint and exhaustive, so we neither double-count nor miss any.
Why `<=` and not `<` on the left. Taking the left element on ties keeps the merge stable and, crucially, does not count equal elements as inversions (an inversion requires strict >). Using < would emit the right element on a tie and wrongly add len(left) - i.
Why long. The recurrence sums up to n(n−1)/2 ≈ 5·10⁹ for n = 10⁵; a 32-bit accumulator silently overflows to a wrong (often negative) answer.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [2, 1, 3, 1, 2]Array state
tie
left 1 <= right 1 → take left
4C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Merge sort already performs every cross-half comparison needed to detect out-of-order pairs — counting inversions is just instrumenting it. 'Augment a known O(n log n) algorithm to answer a counting/aggregation question' is a recurring senior-level technique (also used for range counts via BIT/Fenwick).
ComplexityO(n log n) time, O(n) space — Merge sort makes O(log n) levels, each doing O(n) merge work; counting adds O(1) per merged element, so the total stays O(n log n). The temporary merge buffer is O(n) space.
E · Edge cases and pitfalls7arr = [1, 1, 1, 2, 2] — Every comparison is a tie or in order → 0 inversions; `<=` keeps equals uncounted.Explore edge casesHide edge cases
Edge cases handled
arr = [1, 1, 1, 2, 2]Every comparison is a tie or in order → 0 inversions; `<=` keeps equals uncounted.arr = [7, 8, 9, 1, 2, 3, 4, 5, 6]Each of 7,8,9 exceeds all six smaller values → 18; cross-merge adds them in bulk.arr = [5, 4, 3, 2, 1]Fully reversed → n(n−1)/2 = 10 inversions, the maximum for n=5.
Pitfalls
- Adding 1 instead of (mid - i + 1) / len(left) - i — counts only adjacent inversions.
- Using a 32-bit int accumulator — overflows past ~2·10⁹.
- Using `<` instead of `<=` on the left — counts equal elements as inversions and is unstable.
- Forgetting to copy the merged run back into the array — parent merges then see unsorted halves.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long countInversions(int[] arr) { int[] buffer = new int[arr.length]; return mergeSort(arr, buffer, 0, arr.length - 1); } Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Adding 1 instead of len(left) - i
When you emit a right element early, ALL remaining left elements are inversions, not just one. Adding 1 counts only adjacent inversions and badly undercounts.
Explore the code comparisonHide the code comparison
Adding 1 instead of len(left) - i
When you emit a right element early, ALL remaining left elements are inversions, not just one. Adding 1 counts only adjacent inversions and badly undercounts.
Don't write this
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
count += 1 # WRONG: only one inversionWrite this instead
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
count += len(left) - i # all remaining left elements232-bit overflow
For n = 10⁵ the count can reach ~5·10⁹, which wraps around in a 32-bit int and yields a wrong (often negative) result.
Explore the code comparisonHide the code comparison
32-bit overflow
For n = 10⁵ the count can reach ~5·10⁹, which wraps around in a 32-bit int and yields a wrong (often negative) result.
Don't write this
int count = 0;
// ... count += (mid - i + 1);
return count;Write this instead
long count = 0;
// ... count += (mid - i + 1);
return count;Revise
Carry the pattern into the interview
Pattern to remember
Count inversions as a by-product of the merge step
Code pattern to memorize
merge(left, right):
while i, j in range:
if left[i] <= right[j]: take left[i]; i++
else: take right[j]; j++; count += len(left) - i
# total = count(left) + count(right) + cross-merge countRules to remember
- 1Use long / 64-bit: with n up to 10⁵ the count can be ~5·10⁹, which overflows 32-bit int.
- 2The cross count is added only when you pull from the right half: every left element still unconsumed (
len(left) - iof them) is greater, so each forms an inversion with the right element. - 3Use
left[i] <= right[j](take left on ties) to keep the sort stable and avoid counting equal elements as inversions. - 4Total inversions = inversions(left) + inversions(right) + cross inversions — the standard divide-and-conquer recurrence.
- 5Counting destroys nothing you need: you may sort a copy, since the problem only asks for the count per query.
Use this pattern when
- Count pairs out of order / 'how far from sorted is this array'
- Number of adjacent swaps insertion sort would do (equals inversion count)
- Any 'count pairs (i, j), i < j, with a[i] > a[j]' phrased problem
- Kendall tau distance / measuring rank disagreement between two lists
Choose another pattern when
- n is tiny (≤ ~2000) and clarity matters → the O(n²) double loop is fine
- You need the pairs themselves, not just the count → enumeration, not merge counting
- Values are in a small fixed range and you want online counts → a BIT/Fenwick tree may be cleaner
Interview takeaway
Merge sort already compares every cross-half pair implicitly; counting inversions just tallies the right-before-left pulls. Reusing an O(n log n) sort to answer a counting question is the canonical 'augment a known algorithm' move.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternAugmented merge sort. Counting inversions reuses merge sort's cross-half comparisons, adding len(left) - i whenever a right element is emitted early. O(n log n), 64-bit count. The template generalises to Reverse Pairs and Count of Smaller After Self.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Count of Smaller Numbers After Self (LeetCode 315)Coming soonPer-index inversion counts — merge sort on (value, originalIndex) pairs, or a Fenwick tree.
- Reverse Pairs (LeetCode 493)Coming soonCount pairs with arr[i] > 2·arr[j]; same merge-sort augmentation with a separate counting scan.
- Global and Local InversionsComing soonCompare total inversions to adjacent inversions — a special case solvable in O(n).