Reverse Pairs (LeetCode 493)
You get an integer array nums. A reverse pair is two positions i and j with i < j where the value at i is more than twice the value at j: nums[i] > 2 * nums[j].
Return how many reverse pairs nums holds.
Worked Examples
nums = [1,3,2,3,1]21, and both 3s (at positions 1 and 3) are more than twice it. No other pair works: 2 > 2 * 1 is false.nums = [2,4,3,5,1]31, and 4, 3 and 5 are each more than twice it. 2 > 2 * 1 is false, so 2 does not pair with it.⚖️Formal Constraints & Bounds
1 <= nums.length <= 5 * 104-231 <= nums[i] <= 231 - 1
Core Insight
Every pair i < j crosses the middle of exactly one merge. At that moment both halves are sorted, so for each left value the right values it pairs with form a prefix of the right half, and that prefix only grows: one forward pointer counts all cross pairs in linear time.
Real-World Scenario & Production Applications
Comparing two rankings, spotting how far a feed is out of order, or flagging readings that dropped to less than half of an earlier one all count pairs "earlier and bigger than later". Checking every pair is O(N^2); counting them inside a merge sort takes O(N log N), because the sort does the ordering work the count needs.
Step-by-Step Execution Trace Table
The debugger's first preset, the trap case nums = [3,5,2,1] (answer 3):
| Call | Halves after sorting | Cross pairs counted before merging | count | Merged |
|---|---|---|---|---|
sort_count(0, 2) | [3], [5] | 3 > 2 * 5? no: j stays | 0 | [3, 5] |
sort_count(2, 4) | [2], [1] | 2 > 2 * 1? no | 0 | [1, 2] |
sort_count(0, 4) | [3, 5], [1, 2] | i at 3: 3 > 2 * 1 yes, 3 > 2 * 2 no: j - mid = 1. i at 5: j stays past the 1; 5 > 2 * 2 yes: j - mid = 2 | 3 | [1, 2, 3, 5] |
Counting inside the merge loop instead would visit the 2 while 3 is the waiting left value, see 3 > 4 fail, and never count 5 > 4: it returns 2.
| 1 | Every pair `i < j` lies inside the left half, inside the right half, or crosses the middle; the recursive calls handle the first two kinds, so a call only counts pairs that cross its middle. |
| 2 | Keep this true: when `sort_count(lo, hi)` returns, `nums[lo:hi]` is sorted and every pair inside it is counted. So when both calls return, both halves are sorted. |
| 3 | The shape: a recursive function on `[lo, hi)`: return for one value; recurse on both halves; one pass over the left half with a second index into the right half that is never reset; then an ordinary merge written back into `nums[lo:hi]`. |
| 4 | The trap: count in that separate pass, never inside the merge loop. The merge moves by `nums[a] <= nums[b]`, not by `nums[i] > 2 * nums[j]`, so on `[3,5,2,1]` counting while merging returns 2 instead of 3. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Checking every pair is O(N^2). Merge Sort Counting splits the work the way merge sort does. A pair i < j either sits inside the left half, inside the right half, or crosses the middle, with i on the left and j on the right. The first two kinds are counted by the recursive calls. The third kind is counted in sort_count itself, and here the sort pays off: both halves come back sorted, and a left value only needs the right values smaller than half of it. Those are a prefix of the sorted right half, and as nums[i] grows through the sorted left half, that prefix can only grow, so one pointer j moving forward counts every cross pair. Only then are the halves merged, so the parent sees a sorted range too.
🏃 The Analogy: Two Sorted Teams Comparing Scores
Two teams line up by score, lowest first. For each runner on the left team you want to know how many right-team runners scored less than half of them. You don't compare every pair: a flag walks along the right team, and for each left runner, taken in order, you push it forward past every right runner below half their score. A stronger left runner never needs the flag to go back. Then the teams merge into one sorted line, ready for the next round.
🔑 Why It Works
Both halves are sorted when this loop runs, so nums[mid:j] is exactly the right values that pair with nums[i], and a bigger nums[i] only pushes j further: the whole count is O(N) per merge. The trap is counting inside the merge loop, the way inversions are counted: the merge moves by nums[a] <= nums[b], not by the doubled test, so a right value can be placed before every left value that pairs with it has been seen. On [3,5,2,1] that misses 5 > 2 * 2. Count in its own pass first, then merge.
Counting inside the merge loop (the trap): the merge moves by
nums[a] <= nums[b], not bynums[i] > 2 * nums[j], so the inversion-count stepcount += mid - amisses pairs. On[3,5,2,1]it returns 2 instead of 3; count in its own pass, then merge.>=instead of>: equality is not a pair:[2, 1]has none.Halving instead of doubling:
nums[i] // 2 > nums[j]rounds odd and negative values the wrong way ([7, 3, -4, 3]). In Java or C++,2 * nums[j]needs 64 bits: values reach231 - 1.Restarting the pointer:
j = midinside theforloop keeps the answer right but makes each merge quadratic.Not writing the merge back: the parent's count needs
nums[lo:hi]sorted; forgettingnums[lo:hi] = mergedbreaks every level above.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Count the positions "i < j" with a comparison between the two values, "nums[i] > 2 * nums[j]", on up to 5 * 104 values: every pair would be over a billion checks. A pair condition over positions that only needs the values sorted on each side is the signal for Merge Sort Counting.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule for each left value nums[i]: advance j while j < hi and nums[i] > 2 * nums[j], add count += j - mid, and only after the whole left half is done, merge.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Merging first and counting afterwards: once
nums[lo:hi]is merged, left and right values are mixed and there is no sorted right half left forjto walk.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Merge Sort Counting. Every pair with i before j either sits inside one half of the array or crosses the middle, so I sort and count each half recursively, and count only the crossing pairs myself. When the two halves come back, both are sorted. For a left value, the right values it pairs with are the ones below half of it, which is a prefix of the sorted right half, and that prefix only grows as the left values grow. So one pointer moves forward through the right half and I add its distance from the middle for each left value. Then I merge the halves so my parent gets a sorted range. The trap is counting inside the merge loop like inversions: the merge moves by plain order, not by the doubled condition, so it misses pairs. Each level is linear and there are log N levels:
O(N log N)time,O(N)space.
Complexity & Mathematical Proof
O(N log N)
Look at one call sort_count(lo, hi) with n = hi - lo values. The counting loop runs i over the left half and moves j forward only, so it does at most n steps of i and n / 2 steps of j: O(n). The merge takes each value once: O(n). So T(n) = 2 T(n / 2) + O(n). The recursion has log N levels, and the calls of one level cover all N values once, so each level is O(N). Total: O(N log N).
O(N)
merged holds at most N values at the top call, and each call's buffer is freed before its parent builds its own, so the extra space is O(N). The recursion stack is log N calls deep, O(log N). The answer is one integer.
T(N) = 2 T(N / 2) + O(N) = O(N log N)
Derivation Progression
2 T(n / 2)
sort_count(lo, mid) and sort_count(mid, hi) on halves of size about n / 2.
O(n)
i walks the left half once and j only moves forward through the right half.
O(n)
Each value is appended to merged once and written back once.
O(N log N)
log N levels, each covering N values with O(1) work per value.
Variable Definitions
Number of values, len(nums) (at most 5 * 104)
Size of the range of one call, hi - lo
Memory Architecture & Bounds
O(log N): the recursion depth
O(N): merged, at most N values at the top call
O(1): one integer
Boundary Best / Worst Cases
: every level merges all values
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "i < j", "nums[i] > 2 * nums[j]". Count pairs ordered by position that satisfy a comparison between their values, with n up to : Merge Sort Counting, counting the cross pairs of each merge.
: all pairs are about checks. Merge sort counting is , about steps; a Fenwick tree over compressed values is also .
2 * nums[j] overflows 32 bits in Java and C++ (use 64-bit or long). For data too big for memory, the same count runs as an external merge sort, one sorted run at a time.
Core Algorithmic State Invariants
- Why
jNever Moves Back
If nums[i] > 2 * nums[j] and the next left value is at least nums[i] (the left half is sorted), then it is also greater than 2 * nums[j]. So every right value that paired with one left value pairs with the next one too, and j only moves forward: one pass of j per merge.
Reverse Pairs (LeetCode 493)
You get an integer array nums. A reverse pair is two positions i and j with i < j where the value at i is more than twice the value at j: nums[i] > 2 * nums[j].
Return how many reverse pairs nums holds.
Worked Examples
nums = [1,3,2,3,1]21, and both 3s (at positions 1 and 3) are more than twice it. No other pair works: 2 > 2 * 1 is false.nums = [2,4,3,5,1]31, and 4, 3 and 5 are each more than twice it. 2 > 2 * 1 is false, so 2 does not pair with it.⚖️Formal Constraints & Bounds
1 <= nums.length <= 5 * 104-231 <= nums[i] <= 231 - 1
Core Insight
Every pair i < j crosses the middle of exactly one merge. At that moment both halves are sorted, so for each left value the right values it pairs with form a prefix of the right half, and that prefix only grows: one forward pointer counts all cross pairs in linear time.
Real-World Scenario & Production Applications
Comparing two rankings, spotting how far a feed is out of order, or flagging readings that dropped to less than half of an earlier one all count pairs "earlier and bigger than later". Checking every pair is O(N^2); counting them inside a merge sort takes O(N log N), because the sort does the ordering work the count needs.
Step-by-Step Execution Trace Table
The debugger's first preset, the trap case nums = [3,5,2,1] (answer 3):
| Call | Halves after sorting | Cross pairs counted before merging | count | Merged |
|---|---|---|---|---|
sort_count(0, 2) | [3], [5] | 3 > 2 * 5? no: j stays | 0 | [3, 5] |
sort_count(2, 4) | [2], [1] | 2 > 2 * 1? no | 0 | [1, 2] |
sort_count(0, 4) | [3, 5], [1, 2] | i at 3: 3 > 2 * 1 yes, 3 > 2 * 2 no: j - mid = 1. i at 5: j stays past the 1; 5 > 2 * 2 yes: j - mid = 2 | 3 | [1, 2, 3, 5] |
Counting inside the merge loop instead would visit the 2 while 3 is the waiting left value, see 3 > 4 fail, and never count 5 > 4: it returns 2.
| 1 | Every pair `i < j` lies inside the left half, inside the right half, or crosses the middle; the recursive calls handle the first two kinds, so a call only counts pairs that cross its middle. |
| 2 | Keep this true: when `sort_count(lo, hi)` returns, `nums[lo:hi]` is sorted and every pair inside it is counted. So when both calls return, both halves are sorted. |
| 3 | The shape: a recursive function on `[lo, hi)`: return for one value; recurse on both halves; one pass over the left half with a second index into the right half that is never reset; then an ordinary merge written back into `nums[lo:hi]`. |
| 4 | The trap: count in that separate pass, never inside the merge loop. The merge moves by `nums[a] <= nums[b]`, not by `nums[i] > 2 * nums[j]`, so on `[3,5,2,1]` counting while merging returns 2 instead of 3. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Checking every pair is O(N^2). Merge Sort Counting splits the work the way merge sort does. A pair i < j either sits inside the left half, inside the right half, or crosses the middle, with i on the left and j on the right. The first two kinds are counted by the recursive calls. The third kind is counted in sort_count itself, and here the sort pays off: both halves come back sorted, and a left value only needs the right values smaller than half of it. Those are a prefix of the sorted right half, and as nums[i] grows through the sorted left half, that prefix can only grow, so one pointer j moving forward counts every cross pair. Only then are the halves merged, so the parent sees a sorted range too.
🏃 The Analogy: Two Sorted Teams Comparing Scores
Two teams line up by score, lowest first. For each runner on the left team you want to know how many right-team runners scored less than half of them. You don't compare every pair: a flag walks along the right team, and for each left runner, taken in order, you push it forward past every right runner below half their score. A stronger left runner never needs the flag to go back. Then the teams merge into one sorted line, ready for the next round.
🔑 Why It Works
Both halves are sorted when this loop runs, so nums[mid:j] is exactly the right values that pair with nums[i], and a bigger nums[i] only pushes j further: the whole count is O(N) per merge. The trap is counting inside the merge loop, the way inversions are counted: the merge moves by nums[a] <= nums[b], not by the doubled test, so a right value can be placed before every left value that pairs with it has been seen. On [3,5,2,1] that misses 5 > 2 * 2. Count in its own pass first, then merge.
Counting inside the merge loop (the trap): the merge moves by
nums[a] <= nums[b], not bynums[i] > 2 * nums[j], so the inversion-count stepcount += mid - amisses pairs. On[3,5,2,1]it returns 2 instead of 3; count in its own pass, then merge.>=instead of>: equality is not a pair:[2, 1]has none.Halving instead of doubling:
nums[i] // 2 > nums[j]rounds odd and negative values the wrong way ([7, 3, -4, 3]). In Java or C++,2 * nums[j]needs 64 bits: values reach231 - 1.Restarting the pointer:
j = midinside theforloop keeps the answer right but makes each merge quadratic.Not writing the merge back: the parent's count needs
nums[lo:hi]sorted; forgettingnums[lo:hi] = mergedbreaks every level above.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Count the positions "i < j" with a comparison between the two values, "nums[i] > 2 * nums[j]", on up to 5 * 104 values: every pair would be over a billion checks. A pair condition over positions that only needs the values sorted on each side is the signal for Merge Sort Counting.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule for each left value nums[i]: advance j while j < hi and nums[i] > 2 * nums[j], add count += j - mid, and only after the whole left half is done, merge.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Merging first and counting afterwards: once
nums[lo:hi]is merged, left and right values are mixed and there is no sorted right half left forjto walk.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Merge Sort Counting. Every pair with i before j either sits inside one half of the array or crosses the middle, so I sort and count each half recursively, and count only the crossing pairs myself. When the two halves come back, both are sorted. For a left value, the right values it pairs with are the ones below half of it, which is a prefix of the sorted right half, and that prefix only grows as the left values grow. So one pointer moves forward through the right half and I add its distance from the middle for each left value. Then I merge the halves so my parent gets a sorted range. The trap is counting inside the merge loop like inversions: the merge moves by plain order, not by the doubled condition, so it misses pairs. Each level is linear and there are log N levels:
O(N log N)time,O(N)space.
Complexity & Mathematical Proof
O(N log N)
Look at one call sort_count(lo, hi) with n = hi - lo values. The counting loop runs i over the left half and moves j forward only, so it does at most n steps of i and n / 2 steps of j: O(n). The merge takes each value once: O(n). So T(n) = 2 T(n / 2) + O(n). The recursion has log N levels, and the calls of one level cover all N values once, so each level is O(N). Total: O(N log N).
O(N)
merged holds at most N values at the top call, and each call's buffer is freed before its parent builds its own, so the extra space is O(N). The recursion stack is log N calls deep, O(log N). The answer is one integer.
T(N) = 2 T(N / 2) + O(N) = O(N log N)
Derivation Progression
2 T(n / 2)
sort_count(lo, mid) and sort_count(mid, hi) on halves of size about n / 2.
O(n)
i walks the left half once and j only moves forward through the right half.
O(n)
Each value is appended to merged once and written back once.
O(N log N)
log N levels, each covering N values with O(1) work per value.
Variable Definitions
Number of values, len(nums) (at most 5 * 104)
Size of the range of one call, hi - lo
Memory Architecture & Bounds
O(log N): the recursion depth
O(N): merged, at most N values at the top call
O(1): one integer
Boundary Best / Worst Cases
: every level merges all values
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "i < j", "nums[i] > 2 * nums[j]". Count pairs ordered by position that satisfy a comparison between their values, with n up to : Merge Sort Counting, counting the cross pairs of each merge.
: all pairs are about checks. Merge sort counting is , about steps; a Fenwick tree over compressed values is also .
2 * nums[j] overflows 32 bits in Java and C++ (use 64-bit or long). For data too big for memory, the same count runs as an external merge sort, one sorted run at a time.
Core Algorithmic State Invariants
- Why
jNever Moves Back
If nums[i] > 2 * nums[j] and the next left value is at least nums[i] (the left half is sorted), then it is also greater than 2 * nums[j]. So every right value that paired with one left value pairs with the next one too, and j only moves forward: one pass of j per merge.