Builds on Converging Pointers, which you haven’t finished yet.
Merge Sort Counting (Reverse Pairs, Count of Range Sum)
Reverse Pairs (LC 493)(opens leetcode.com)
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.
1, and both 3s (at positions 1 and 3) are more than twice it. No other pair works: 2 > 2 * 1 is false.Merge Sort Counting
pairs i < j ➔ count across two sorted halves ➔ mergei < j whose values satisfy a comparison (an earlier value bigger than a later one, more than twice it, or a difference within a range), and checking every pair is too slow.| 1 | def reverse_pairs(nums: list[int]) -> int: |
| 2 | """Reverse Pairs: count the pairs that cross the middle while both halves are sorted, then merge. |
| 3 | Time: O(N log N) | Space: O(N) |
| 4 | """ |
| 5 | def sort_count(lo: int, hi: int) -> int: |
| 6 | # 1. Handle One Value, Then Count Each Half On Its Own: |
| 7 | # A range of one value holds no pair; otherwise the recursive calls count every pair |
| 8 | # that does not cross this range's middle, and hand back two sorted halves. |
| 9 | if hi - lo <= 1: |
| 10 | return 0 |
| 11 | mid = (lo + hi) // 2 |
| 12 | count = sort_count(lo, mid) + sort_count(mid, hi) |
| 13 | |
| 14 | # 2. Count The Pairs That Cross The Middle, While Both Halves Are Still Sorted: |
| 15 | # nums[i] only grows as i moves through the sorted left half, so the right values |
| 16 | # that pair with it, nums[mid:j], can only grow too; j never has to move back. |
| 17 | j = mid |
| 18 | for i in range(lo, mid): |
| 19 | while j < hi and nums[i] > 2 * nums[j]: |
| 20 | j += 1 |
| 21 | count += j - mid |
| 22 | |
| 23 | # 3. Merge The Two Sorted Halves, Now That Counting Is Done: |
| 24 | # The merge moves by plain order, nums[a] <= nums[b], not by the pair's own test, so |
| 25 | # counting must happen first, in its own pass; merging afterwards hands the parent a |
| 26 | # sorted range. |
| 27 | merged: list[int] = [] |
| 28 | a, b = lo, mid |
| 29 | while a < mid and b < hi: |
| 30 | if nums[a] <= nums[b]: |
| 31 | merged.append(nums[a]) |
| 32 | a += 1 |
| 33 | else: |
| 34 | merged.append(nums[b]) |
| 35 | b += 1 |
| 36 | merged.extend(nums[a:mid]) |
| 37 | merged.extend(nums[b:hi]) |
| 38 | nums[lo:hi] = merged |
| 39 | return count |
| 40 | |
| 41 | return sort_count(0, len(nums)) |
sort_count(lo, hi) returns, nums[lo:hi] is sorted and every pair inside [lo, hi) is counted exactly once; cross pairs are counted while both halves are sorted, before they are merged.Every pair i < j either sits inside one half of the range or crosses its middle, so let the recursive calls count the pairs inside each half and count only the crossing pairs yourself, at the moment both halves come back sorted. Sorted halves are what make that fast: the right values that pair with nums[i] form a prefix nums[mid:j] of the right half, and as nums[i] grows through the sorted left half that prefix only grows, so one pointer j that never moves back counts all of them with count += j - mid; merging afterwards hands the parent a sorted range, which keeps the argument true one level up. The trap is counting inside the merge loop, the way inversions are counted: the merge moves by nums[a] <= nums[b], not by the pair's own test nums[i] > 2 * nums[j], so on [3,5,2,1] it misses 5 > 2 * 2 and returns 2 instead of 3. Count in a separate pass, then merge.
See it run
Merge sort counting: count the crossing pairs, then merge
lo, mid, hi 0, 0, 4j -count 0pairs found 0
Each column is one position in nums. The pair test is nums[i] > 2 * nums[j], with i in the left half and j in the right half.
left halfthe sorted left half of the current rangeright halfthe sorted right half of the current rangeithe left value being testedjthe right value that j points atmergedthe range just merged into sorted order
Start with nums = [3, 5, 2, 1]. sort_count splits each range at mid until a range holds one value.
Gotcha 1 of 5
- The trap
Gotcha 1: Counting pairs inside the merge loop
Mistakeelse: if nums[a] > 2 * nums[b]: count += mid - a merged.append(nums[b]) b += 1Fixj = mid for i in range(lo, mid): while j < hi and nums[i] > 2 * nums[j]: j += 1 count += j - midWhat happens: The merge moves
aandbby the testnums[a] <= nums[b]. The pair test is a different one,nums[i] > 2 * nums[j]. So the merge can move past a right value before it is tested against the larger left values. The separate pass tests every left value with its own pointerj.Example: nums = [3, 5, 2, 1]Mistake: returns 2Fix: returns 3
- Values change and questions arrive in between, as in Range Sum Query - Mutable (LC 307): a merge sort counts once over a fixed array, so updates mixed with queries call for a Fenwick tree. See Fenwick Tree
Deep Dive
Every pair is counted exactly once
A pair i < j has three possible positions inside the range [lo, hi). Both indices can be in the left half, both can be in the right half, or i can be in the left half and j in the right half.
The two recursive calls count the first two kinds. The code after them counts the third kind, the pairs that cross the middle. No pair belongs to two kinds, so the total is exact.
Example: nums = [3, 5, 2, 1]. The left half [3, 5] has no pair with 3 > 2 * 5. The right half [2, 1] has no pair with 2 > 2 * 1. The crossing pairs are (3, 1), (5, 2) and (5, 1). The pair (3, 2) fails because 3 > 4 is false. The answer is 3.
One pointer j that never moves back
When the counting starts, both halves are sorted. At the top call for [3, 5, 2, 1], the left half is [3, 5] and the right half is [1, 2].
For i = 0, nums[i] = 3. The loop moves j while nums[i] > 2 * nums[j]. 3 > 2 * 1 is true, so j moves to the value 2. 3 > 2 * 2 is false, so j stops. The right values that pair with 3 are the prefix nums[mid:j], which has j - mid = 1 value.
For i = 1, nums[i] = 5. The left half is sorted, so 5 is at least 3, and every right value that paired with 3 pairs with 5 too. So j does not go back. It continues from where it stopped. 5 > 2 * 2 is true, so j reaches hi, and the count grows by j - mid = 2.
The right half is sorted too, so the values that pair with nums[i] always form a prefix of it. In total, i moves at most mid - lo times and j at most hi - mid times. One counting pass is O(hi - lo).
Why counting and merging are two passes
The merge moves by the test nums[a] <= nums[b]. The pair test is nums[i] > 2 * nums[j]. These are different tests, and a merge that counts with the pair test moves past values before they are tested.
Trace the merge for halves [3, 5] and [1, 2]. It compares 3 and 1 and takes 1. The pair test 3 > 2 * 1 is true, so the count grows by mid - a = 2. That counts 3 and 5. Next it compares 3 and 2 and takes 2. The pair test 3 > 4 is false. The right half is now used up, so the merge never compares 5 with 2.
The pair (5, 2) has 5 > 4, which is true, but it was never tested. The count ends at 2 and the correct answer is 3. The separate counting pass gives 5 its own turn, because every i moves j on its own.
So the order is fixed: count while both halves are sorted, then merge to give the parent a sorted range.
Cost, and the same shape elsewhere
Each call does O(hi - lo) work after its two recursive calls: one counting pass and one merge. The recursion has about log2 N levels, and each level does O(N) work in total. The time is O(N log N). The merged list takes O(N) space.
Count of Range Sum (LC 327) uses the same shape on prefix sums. Let s hold the prefix sums, with s[0] = 0. For each i in the left half, keep two pointers: k is the first right index with s[k] - s[i] >= lower, and j is the first with s[j] - s[i] > upper. Both only move forward, and count += j - k. For nums = [-2, 5, -1] with lower = -2 and upper = 2, the answer is 3.
Count of Smaller Numbers After Self (LC 315) is also a crossing count, but it needs the original index of each value. A Fenwick Tree over value ranks is the usual shorter solution.
In languages with 32-bit integers, 2 * nums[j] can overflow. Compute it in 64 bits. Python integers have no limit.
60-Second Pitch
"Every pair i < j is either inside one half or crosses the middle. So I let the recursive calls count the inside pairs, and I count only the crossing pairs. That is fast when both halves are sorted. For each left value, the right values that pair with it are a prefix of the right half. A larger left value keeps that prefix, so one pointer j never moves back and the pass is linear. I count in a separate pass, and then merge. If I counted inside the merge, the merge would skip right values before testing them, because it moves by order and not by the pair test. There are about log N levels with O(N) work each. The time is O(N log N) and the space is O(N)."
Common Questions
- Why does the pointer
jnever move back? The left half is sorted, so
nums[i]does not decrease asigrows. Ifnums[i] > 2 * nums[j], the next left value is at least as large and passes the same test. Sojonly moves forward, and the pass is linear.- Why not count inside the merge, as in Count Inversions?
For plain inversions, the pair test
nums[a] > nums[b]is the same test that the merge uses to move. For Reverse Pairs (LC 493), the pair test isnums[i] > 2 * nums[j], which is different from the merge test. The merge can skip a right value before the pair test sees it. So count first and merge after.- Can a Fenwick tree solve Reverse Pairs (LC 493) too?
Yes. Compress the values of
numsand of2 * numsinto ranks. Scan from the left. For eachnums[j], query how many earlier values are greater than2 * nums[j], then addnums[j]to the tree. The time isO(N log N). The merge sort version needs no compression.- What is the space cost, and can it be reduced?
The
mergedlist usesO(N)space, and the recursion usesO(log N). An in-place merge is possible but complex. Interviews accept theO(N)buffer.- How does the idea change for Count of Range Sum (LC 327)?
Work on prefix sums. For each left prefix
s[i], count the right prefixess[j]withlower <= s[j] - s[i] <= upper. Those form a range of right indices between two pointerskandj, and both move forward. The count isj - k. Then merge.
SWE Reasoning
Spot it
- The question counts pairs
i < jwhere the values satisfy a comparison: bigger than twice, smaller than, or a difference in a range. - Checking every pair is O(N^2), and N is large enough to rule that out.
- The comparison depends only on the two values, so the order of values inside one half does not change which pairs cross the middle.
- The same shape appears for prefix sums, as in Count of Range Sum (LC 327).
The invariant, step by step
sort_count(lo, hi)returns the number of pairs inside[lo, hi)and leavesnums[lo:hi]sorted.- A range of one value has no pair, so it returns 0.
- Otherwise the two recursive calls count the pairs inside each half and leave both halves sorted.
- The counting pass moves
ithrough the left half andjthrough the right half. For eachi,jstops at the first right value that failsnums[i] > 2 * nums[j], andcount += j - mid. jnever moves back, because a largernums[i]keeps every right value that a smaller one paired with.- Only after counting does the merge sort the range, so the parent receives a sorted
nums[lo:hi]and the invariant holds one level up.
Traps
- Counting inside the merge loop. The merge moves by
nums[a] <= nums[b], not by the pair test.[3, 5, 2, 1]returns 2 and not 3. sort_count(lo, mid + 1).hiis exclusive, so this call repeats the same range for two values. Python raisesRecursionError.- Resetting
j = midfor everyi. The answer stays correct, but each counting pass becomes quadratic, so the total is O(N^2). >=in the test. The problem needs a strictly greater value. For[2, 1],>=returns 1 and the answer is 0.nums[i] // 2 > nums[j]. Integer division rounds down. For[7, 3]it returns 0 and the answer is 1. Usenums[i] > 2 * nums[j].
Practice
Builds on Converging Pointers, which you haven’t finished yet.
Merge Sort Counting (Reverse Pairs, Count of Range Sum)
Reverse Pairs (LC 493)(opens leetcode.com)
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.
1, and both 3s (at positions 1 and 3) are more than twice it. No other pair works: 2 > 2 * 1 is false.Merge Sort Counting
pairs i < j ➔ count across two sorted halves ➔ mergei < j whose values satisfy a comparison (an earlier value bigger than a later one, more than twice it, or a difference within a range), and checking every pair is too slow.| 1 | def reverse_pairs(nums: list[int]) -> int: |
| 2 | """Reverse Pairs: count the pairs that cross the middle while both halves are sorted, then merge. |
| 3 | Time: O(N log N) | Space: O(N) |
| 4 | """ |
| 5 | def sort_count(lo: int, hi: int) -> int: |
| 6 | # 1. Handle One Value, Then Count Each Half On Its Own: |
| 7 | # A range of one value holds no pair; otherwise the recursive calls count every pair |
| 8 | # that does not cross this range's middle, and hand back two sorted halves. |
| 9 | if hi - lo <= 1: |
| 10 | return 0 |
| 11 | mid = (lo + hi) // 2 |
| 12 | count = sort_count(lo, mid) + sort_count(mid, hi) |
| 13 | |
| 14 | # 2. Count The Pairs That Cross The Middle, While Both Halves Are Still Sorted: |
| 15 | # nums[i] only grows as i moves through the sorted left half, so the right values |
| 16 | # that pair with it, nums[mid:j], can only grow too; j never has to move back. |
| 17 | j = mid |
| 18 | for i in range(lo, mid): |
| 19 | while j < hi and nums[i] > 2 * nums[j]: |
| 20 | j += 1 |
| 21 | count += j - mid |
| 22 | |
| 23 | # 3. Merge The Two Sorted Halves, Now That Counting Is Done: |
| 24 | # The merge moves by plain order, nums[a] <= nums[b], not by the pair's own test, so |
| 25 | # counting must happen first, in its own pass; merging afterwards hands the parent a |
| 26 | # sorted range. |
| 27 | merged: list[int] = [] |
| 28 | a, b = lo, mid |
| 29 | while a < mid and b < hi: |
| 30 | if nums[a] <= nums[b]: |
| 31 | merged.append(nums[a]) |
| 32 | a += 1 |
| 33 | else: |
| 34 | merged.append(nums[b]) |
| 35 | b += 1 |
| 36 | merged.extend(nums[a:mid]) |
| 37 | merged.extend(nums[b:hi]) |
| 38 | nums[lo:hi] = merged |
| 39 | return count |
| 40 | |
| 41 | return sort_count(0, len(nums)) |
sort_count(lo, hi) returns, nums[lo:hi] is sorted and every pair inside [lo, hi) is counted exactly once; cross pairs are counted while both halves are sorted, before they are merged.Every pair i < j either sits inside one half of the range or crosses its middle, so let the recursive calls count the pairs inside each half and count only the crossing pairs yourself, at the moment both halves come back sorted. Sorted halves are what make that fast: the right values that pair with nums[i] form a prefix nums[mid:j] of the right half, and as nums[i] grows through the sorted left half that prefix only grows, so one pointer j that never moves back counts all of them with count += j - mid; merging afterwards hands the parent a sorted range, which keeps the argument true one level up. The trap is counting inside the merge loop, the way inversions are counted: the merge moves by nums[a] <= nums[b], not by the pair's own test nums[i] > 2 * nums[j], so on [3,5,2,1] it misses 5 > 2 * 2 and returns 2 instead of 3. Count in a separate pass, then merge.
See it run
Merge sort counting: count the crossing pairs, then merge
lo, mid, hi 0, 0, 4j -count 0pairs found 0
Each column is one position in nums. The pair test is nums[i] > 2 * nums[j], with i in the left half and j in the right half.
left halfthe sorted left half of the current rangeright halfthe sorted right half of the current rangeithe left value being testedjthe right value that j points atmergedthe range just merged into sorted order
Start with nums = [3, 5, 2, 1]. sort_count splits each range at mid until a range holds one value.
Gotcha 1 of 5
- The trap
Gotcha 1: Counting pairs inside the merge loop
Mistakeelse: if nums[a] > 2 * nums[b]: count += mid - a merged.append(nums[b]) b += 1Fixj = mid for i in range(lo, mid): while j < hi and nums[i] > 2 * nums[j]: j += 1 count += j - midWhat happens: The merge moves
aandbby the testnums[a] <= nums[b]. The pair test is a different one,nums[i] > 2 * nums[j]. So the merge can move past a right value before it is tested against the larger left values. The separate pass tests every left value with its own pointerj.Example: nums = [3, 5, 2, 1]Mistake: returns 2Fix: returns 3
- Values change and questions arrive in between, as in Range Sum Query - Mutable (LC 307): a merge sort counts once over a fixed array, so updates mixed with queries call for a Fenwick tree. See Fenwick Tree
Deep Dive
Every pair is counted exactly once
A pair i < j has three possible positions inside the range [lo, hi). Both indices can be in the left half, both can be in the right half, or i can be in the left half and j in the right half.
The two recursive calls count the first two kinds. The code after them counts the third kind, the pairs that cross the middle. No pair belongs to two kinds, so the total is exact.
Example: nums = [3, 5, 2, 1]. The left half [3, 5] has no pair with 3 > 2 * 5. The right half [2, 1] has no pair with 2 > 2 * 1. The crossing pairs are (3, 1), (5, 2) and (5, 1). The pair (3, 2) fails because 3 > 4 is false. The answer is 3.
One pointer j that never moves back
When the counting starts, both halves are sorted. At the top call for [3, 5, 2, 1], the left half is [3, 5] and the right half is [1, 2].
For i = 0, nums[i] = 3. The loop moves j while nums[i] > 2 * nums[j]. 3 > 2 * 1 is true, so j moves to the value 2. 3 > 2 * 2 is false, so j stops. The right values that pair with 3 are the prefix nums[mid:j], which has j - mid = 1 value.
For i = 1, nums[i] = 5. The left half is sorted, so 5 is at least 3, and every right value that paired with 3 pairs with 5 too. So j does not go back. It continues from where it stopped. 5 > 2 * 2 is true, so j reaches hi, and the count grows by j - mid = 2.
The right half is sorted too, so the values that pair with nums[i] always form a prefix of it. In total, i moves at most mid - lo times and j at most hi - mid times. One counting pass is O(hi - lo).
Why counting and merging are two passes
The merge moves by the test nums[a] <= nums[b]. The pair test is nums[i] > 2 * nums[j]. These are different tests, and a merge that counts with the pair test moves past values before they are tested.
Trace the merge for halves [3, 5] and [1, 2]. It compares 3 and 1 and takes 1. The pair test 3 > 2 * 1 is true, so the count grows by mid - a = 2. That counts 3 and 5. Next it compares 3 and 2 and takes 2. The pair test 3 > 4 is false. The right half is now used up, so the merge never compares 5 with 2.
The pair (5, 2) has 5 > 4, which is true, but it was never tested. The count ends at 2 and the correct answer is 3. The separate counting pass gives 5 its own turn, because every i moves j on its own.
So the order is fixed: count while both halves are sorted, then merge to give the parent a sorted range.
Cost, and the same shape elsewhere
Each call does O(hi - lo) work after its two recursive calls: one counting pass and one merge. The recursion has about log2 N levels, and each level does O(N) work in total. The time is O(N log N). The merged list takes O(N) space.
Count of Range Sum (LC 327) uses the same shape on prefix sums. Let s hold the prefix sums, with s[0] = 0. For each i in the left half, keep two pointers: k is the first right index with s[k] - s[i] >= lower, and j is the first with s[j] - s[i] > upper. Both only move forward, and count += j - k. For nums = [-2, 5, -1] with lower = -2 and upper = 2, the answer is 3.
Count of Smaller Numbers After Self (LC 315) is also a crossing count, but it needs the original index of each value. A Fenwick Tree over value ranks is the usual shorter solution.
In languages with 32-bit integers, 2 * nums[j] can overflow. Compute it in 64 bits. Python integers have no limit.
60-Second Pitch
"Every pair i < j is either inside one half or crosses the middle. So I let the recursive calls count the inside pairs, and I count only the crossing pairs. That is fast when both halves are sorted. For each left value, the right values that pair with it are a prefix of the right half. A larger left value keeps that prefix, so one pointer j never moves back and the pass is linear. I count in a separate pass, and then merge. If I counted inside the merge, the merge would skip right values before testing them, because it moves by order and not by the pair test. There are about log N levels with O(N) work each. The time is O(N log N) and the space is O(N)."
Common Questions
- Why does the pointer
jnever move back? The left half is sorted, so
nums[i]does not decrease asigrows. Ifnums[i] > 2 * nums[j], the next left value is at least as large and passes the same test. Sojonly moves forward, and the pass is linear.- Why not count inside the merge, as in Count Inversions?
For plain inversions, the pair test
nums[a] > nums[b]is the same test that the merge uses to move. For Reverse Pairs (LC 493), the pair test isnums[i] > 2 * nums[j], which is different from the merge test. The merge can skip a right value before the pair test sees it. So count first and merge after.- Can a Fenwick tree solve Reverse Pairs (LC 493) too?
Yes. Compress the values of
numsand of2 * numsinto ranks. Scan from the left. For eachnums[j], query how many earlier values are greater than2 * nums[j], then addnums[j]to the tree. The time isO(N log N). The merge sort version needs no compression.- What is the space cost, and can it be reduced?
The
mergedlist usesO(N)space, and the recursion usesO(log N). An in-place merge is possible but complex. Interviews accept theO(N)buffer.- How does the idea change for Count of Range Sum (LC 327)?
Work on prefix sums. For each left prefix
s[i], count the right prefixess[j]withlower <= s[j] - s[i] <= upper. Those form a range of right indices between two pointerskandj, and both move forward. The count isj - k. Then merge.
SWE Reasoning
Spot it
- The question counts pairs
i < jwhere the values satisfy a comparison: bigger than twice, smaller than, or a difference in a range. - Checking every pair is O(N^2), and N is large enough to rule that out.
- The comparison depends only on the two values, so the order of values inside one half does not change which pairs cross the middle.
- The same shape appears for prefix sums, as in Count of Range Sum (LC 327).
The invariant, step by step
sort_count(lo, hi)returns the number of pairs inside[lo, hi)and leavesnums[lo:hi]sorted.- A range of one value has no pair, so it returns 0.
- Otherwise the two recursive calls count the pairs inside each half and leave both halves sorted.
- The counting pass moves
ithrough the left half andjthrough the right half. For eachi,jstops at the first right value that failsnums[i] > 2 * nums[j], andcount += j - mid. jnever moves back, because a largernums[i]keeps every right value that a smaller one paired with.- Only after counting does the merge sort the range, so the parent receives a sorted
nums[lo:hi]and the invariant holds one level up.
Traps
- Counting inside the merge loop. The merge moves by
nums[a] <= nums[b], not by the pair test.[3, 5, 2, 1]returns 2 and not 3. sort_count(lo, mid + 1).hiis exclusive, so this call repeats the same range for two values. Python raisesRecursionError.- Resetting
j = midfor everyi. The answer stays correct, but each counting pass becomes quadratic, so the total is O(N^2). >=in the test. The problem needs a strictly greater value. For[2, 1],>=returns 1 and the answer is 0.nums[i] // 2 > nums[j]. Integer division rounds down. For[7, 3]it returns 0 and the answer is 1. Usenums[i] > 2 * nums[j].