Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
An inversion is a pair (i, j) with i < j but nums[i] > nums[j]. Counting them brute-force is O(n²). The interview answer is a modified merge sort: during the merge, when you pull an element from the right half before the left, every remaining element in the left half forms an inversion — add (mid − i + 1) at once, giving O(n log n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you connect 'count out-of-order pairs' to merge sort, and whether you get the cross-count right: adding all remaining left elements in one shot rather than incrementing by one.
Where candidates slip
Counting one inversion per right-element pick instead of (mid − i + 1), using `<` so equal elements get miscounted, or overflowing a 32-bit counter.
How to stand out
State the three-part recurrence (left + right + cross), explain why the left half being sorted lets you batch-count, and note the long overflow up front.
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 approachFirst decision previewCount inversionsn small enough for O(n²)?YesNoExplore the full treeCollapse the tree
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 — Check Every Pair (Baseline)
1Hint 1Explore hintHide hint
An inversion is literally a pair (i, j) with i < j and nums[i] > nums[j]. What's the most direct way to count such pairs?
2Hint 2Explore hintHide hint
Two nested loops: outer i, inner j > i. Increment a counter whenever nums[i] > nums[j].
3Hint 3Explore hintHide hint
This is correct but O(n²). For n = 10⁵ that's 10¹⁰ comparisons — far too slow. What sorting algorithm naturally compares cross-pairs?
A · Core idea
Translate the definition straight into code: for every i, scan every later j and increment a counter when nums[i] > nums[j].
Why it's the right way to understand the problem. Before optimizing, make the definition concrete — an inversion is an out-of-order pair, and the double loop counts exactly those. Running it on [2, 4, 1, 3, 5] and watching it find (2,1), (4,1), (4,3) confirms your mental model and gives you a reference oracle to test the fast version against.
Why `j` starts at `i + 1`. Inversions are defined on i < j, so the inner loop begins just past i. This counts each unordered pair exactly once and never compares an element with itself.
Why it doesn't survive the constraints. At n = 10⁵ the loop does ~`5 × 10⁹` comparisons — seconds to minutes, a guaranteed time-limit exceeded. The cost is fundamentally quadratic because it inspects pairs independently, learning nothing reusable. The fix is to count pairs in bulk, which is exactly what a merge does.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [2, 4, 1, 3, 5]Array state
i=1 (4)
4 > 1 and 4 > 3 → +2
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 double loop is the definition made literal — perfect for correctness, useless for scale. Use it as the oracle you validate the merge-sort solution against.
ComplexityO(n²) time, O(1) space — Every ordered pair (i, j) with i < j is examined once: n(n−1)/2 comparisons → O(n²). Only a counter is stored.
E · Edge cases and pitfalls3Using >= and counting equal elements as inversions.Explore edge casesHide edge cases
Pitfalls
- Using >= and counting equal elements as inversions.
- Storing the count in a 32-bit int — overflows for large n.
- Shipping this for n = 10⁵ and timing out.
Approach 2 of 2 · Optimal
Modified Merge Sort (Optimal)
1Hint 1Explore hintHide hint
Split the array in half, recursively count inversions in each half. What kind of inversions are left to count after that?
2Hint 2Explore hintHide hint
Cross-half inversions: i in the left half, j in the right half. If both halves are sorted, can you count these efficiently while merging them?
3Hint 3Explore hintHide hint
During merge, when right[j] < left[i], element right[j] is smaller than left[i] AND every left element after i (they're sorted). So add (number of remaining left elements) all at once.
A · Core idea
Run a standard merge sort, but during each merge tally the inversions that cross the two halves. The total is inversions(left) + inversions(right) + cross-half inversions.
Why splitting captures every inversion exactly once. Any inversion (i, j) has both indices in the left half, both in the right half, or one in each. The recursive calls handle the first two cases; the merge handles the third. Because the three categories are disjoint and exhaustive, summing them counts each inversion once — no double counting, no misses. This is the divide-and-conquer skeleton.
The key insight — batch counting during merge. When merging two sorted halves, you compare left[i] and right[j]. If right[j] < left[i], then right[j] is smaller than left[i] — but since the left half is sorted ascending, right[j] is also smaller than left[i+1], left[i+2], … all the way to mid. So this single right element forms an inversion with every remaining left element. Instead of counting them one by one, add (mid − i + 1) in one stroke. That batching is precisely what removes the quadratic factor.
Why `<=` and not `<` in the comparison. When left[i] == right[j], that pair is not an inversion (it needs strict greater-than). Taking the left element first on ties (left[i] <= right[j] → take left) avoids counting equal elements as inversions and also keeps the sort stable. Flip it to < and you over-count every duplicate that straddles the split.
Why a long, and why O(n) space. The maximum inversion count is n(n−1)/2, about 5 × 10⁹ for n = 10⁵ — past the 32-bit range, so the accumulator must be long. The merge needs a temporary buffer of size O(n); that's the space cost, not the recursion stack (which is O(log n)).
Why this generalizes. The same 'count something during the merge' template solves 'count smaller elements to the right', 'reverse pairs' (nums[i] > 2·nums[j]), and 'range sum count'. Recognizing inversions as the prototypical instance is the transferable skill.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
merging sorted halves [2, 4] and [1, 3] of [2, 4, 1, 3]Array state
take 1
1 < 2 → +2 (both 2 and 4 remain)
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
Because the left half is sorted, one right element that jumps ahead is simultaneously smaller than all remaining left elements — so you count k inversions in O(1) instead of k steps. That batch count is the entire reason the algorithm is O(n log n).
ComplexityO(n log n) time, O(n) space — Merge sort's recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n). The inversion counting adds only O(1) work per merge comparison, so it doesn't change the bound. The temporary merge buffer needs O(n) space.
E · Edge cases and pitfalls7nums = [1, 2, 3] — Every merge always takes from the left first; cross count stays 0. Returns 0.Explore edge casesHide edge cases
Edge cases handled
nums = [1, 2, 3]Every merge always takes from the left first; cross count stays 0. Returns 0.nums = [3, 2, 1]Maximum inversions for n=3: returns 3.nums = [2, 2, 2]Equal elements; <= takes left first so no inversions are counted. Returns 0.
Pitfalls
- Incrementing count by 1 instead of (mid − i + 1) — silently undercounts.
- Using < instead of <=, miscounting equal straddling elements.
- Storing the count in an int — overflows near 5 × 10⁹.
- Forgetting to add the two recursive returns to the cross count.
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.
1Incrementing by one instead of batching
When right[j] is taken, it inverts with EVERY remaining left element, not just left[i]. Adding 1 undercounts.
Explore the code comparisonHide the code comparison
Incrementing by one instead of batching
When right[j] is taken, it inverts with EVERY remaining left element, not just left[i]. Adding 1 undercounts.
Don't write this
} else {
buf[k++] = a[j++];
count += 1; // only counts one inversion
}Write this instead
} else {
buf[k++] = a[j++];
count += (mid - i + 1); // all remaining left elements
}2Strict < miscounts equals
With <, when left[i] == right[j] you take the right element and count it as an inversion — but equal pairs are not inversions.
Explore the code comparisonHide the code comparison
Strict < miscounts equals
With <, when left[i] == right[j] you take the right element and count it as an inversion — but equal pairs are not inversions.
Don't write this
if left[i] < right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
cross += len(left) - i # over-counts when equalWrite this instead
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
cross += len(left) - i332-bit overflow on the count
Maximum inversions n(n−1)/2 is ~5 billion for n = 10⁵, beyond Integer.MAX_VALUE. Accumulate in a long.
Explore the code comparisonHide the code comparison
32-bit overflow on the count
Maximum inversions n(n−1)/2 is ~5 billion for n = 10⁵, beyond Integer.MAX_VALUE. Accumulate in a long.
Don't write this
int count = 0; // overflows for large reverse-sorted inputWrite this instead
long count = 0;Revise
Carry the pattern into the interview
Pattern to remember
Modified merge sort — count cross-half inversions during the merge step
Code pattern to memorize
merge(left, right):
while i in left and j in right:
if left[i] <= right[j]: take left[i]; i++
else: take right[j]; j++; inversions += (len(left) - i)Rules to remember
- 1Count inversions during the merge, the moment a right element is picked before left elements remain: add
(mid − i + 1)— all leftover left elements at once, not one. - 2Use
<=(not<) when comparing left vs right so equal elements aren't miscounted as inversions — equal pairs are not inversions. - 3The inversion count can be as large as
n(n−1)/2 ≈ 5 × 10⁹forn = 10⁵— use a 64-bitlong, notint. - 4Total inversions = (inversions in left half) + (inversions in right half) + (cross-half inversions). Don't forget to sum the recursive returns.
- 5The array gets sorted as a side effect; if the caller needs the original order, sort a copy.
Use this pattern when
- Counting how 'out of order' an array is (number of swaps a bubble sort would do)
- Measuring rank correlation / similarity between two orderings
- Any 'count pairs where i < j and some order condition holds' over a large array
- When an O(n²) pair scan is too slow and the condition is comparison-based
Choose another pattern when
- n is tiny → the brute force double loop is simpler and fine
- You only need to know if *any* inversion exists → just check if the array is sorted in O(n)
- Values are bounded small integers → a Binary Indexed Tree (BIT) over values is an alternative O(n log V)
Interview takeaway
Inversion counting is the canonical 'piggyback a count onto merge sort' problem. The single insight — when a right element jumps ahead of k remaining left elements, that's k inversions at once — is what turns O(n²) into O(n log n).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCounting work piggybacked onto merge sort's divide-and-conquer. The reusable template: split, recurse, then count cross-boundary pairs during the merge using the sortedness of each half to batch the count. It also solves count-smaller-to-the-right and reverse-pairs.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Merge Sort & Count InversionsThe same algorithm presented as a sorting tutorial with the inversion count as a side product.
- Count of Smaller Numbers After SelfPer-index version: how many elements to the right are smaller — track indices through the merge or use a BIT.
- Reverse Pairs (nums[i] > 2·nums[j])Same merge-sort scaffold, but add a separate counting pass per merge with the 2× condition before merging.