Reverse Pairs
Reverse Pairs: count pairs (i, j) with i < j and nums[i] > 2 * nums[j].
- 1 <= nums.length <= 5 * 10⁴
- -2³¹ <= nums[i] <= 2³¹ - 1
Intuition
Reverse pairs counts pairs (i, j) with i < j and nums[i] > 2 × nums[j]. Checking every pair is O(n²), and the structure that beats it is the same one behind counting inversions — merge sort with a counting step.
Split the array in half. Pairs lying entirely within one half are counted by recursion. What remains is pairs that cross the midpoint, and those are what the merge level handles.
Once both halves are sorted, counting crossing pairs becomes a linear sweep. For a fixed left element, the right-half values satisfying left > 2 × right are the smallest ones — they form a prefix of the sorted right half. And as the left element grows, that prefix can only grow too, so a single pointer advances monotonically across the whole left half:
- Two pointers count every crossing pair in one linear pass, without ever comparing pairs individually.
The detail that trips people up is that this counting must happen before the merge, in its own separate sweep. The condition uses 2 × nums[j], not the plain comparison the merge performs, so the two cannot be folded into one loop the way they can for ordinary inversion counting.
One practical caution: 2 * nums[j] overflows a 32-bit integer when values approach the limit. Compare nums[i] > 2L * nums[j] in 64-bit arithmetic, or rearrange to avoid the multiplication.
Count-inversions with a twist — the condition nums[i] > 2 * nums[j] is not the same as the merge comparison, so the counting cannot ride along inside the merge itself. It needs its own two-pointer sweep over the two sorted halves before merging. Recognising when a counting condition diverges from the sort order is what tells you to separate the passes.
Approach
Before reading on: price up what the direct approach costs here, then ask what you would need to remember from the left to avoid re-scanning. Aim for O(n log n) time and O(n) space.
Divide and count separately
Recurse on both halves to count pairs contained within each. What is left is exactly the crossing pairs, which the current level counts — the standard divide-and-conquer decomposition.
Count before merging
Run a dedicated two-pointer sweep over the two sorted halves before the merge. The condition involves 2 × nums[j], which the merge's own comparison does not test, so the two steps cannot be combined.
Advance the right pointer monotonically
For each left element, advance j while nums[i] > 2 * nums[j]. Since the left half is sorted, j never needs to move backwards — one pass over each half counts every crossing pair.
Add the prefix length
After advancing, the number of qualifying right elements is j - rightStart. Add that to the running total. Counting pairs individually would put the quadratic cost straight back.
Merge to restore order
After counting, merge the two halves so the parent call receives a sorted range. The sortedness is a precondition for the counting sweep, so it must be maintained at every level.
Guard the multiplication
2 * nums[j] overflows a 32-bit integer for large values, silently reversing the comparison. Use 64-bit arithmetic for the doubling — this is the usual cause of a wrong answer on the extreme tests.
Cost of the approach
Log n levels each doing O(n) counting and O(n) merging give O(n log n) time and O(n) space. A Binary Indexed Tree over compressed values reaches the same bound.
Solution & live demo
Common pitfalls
Counting inside the merge comparison
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
count += len(left) - ij = mid
for i in range(lo, mid):
while j < hi and nums[i] > 2 * nums[j]: j += 1
count += j - midThat counts pairs where left[i] > right[j], not where left[i] > 2 * right[j] — a strictly different and much larger set. The doubled condition needs a separate sweep before the halves are merged.
Resetting the right pointer for each left element
for i in range(lo, mid):
j = mid
while j < hi and nums[i] > 2 * nums[j]: j += 1j = mid
for i in range(lo, mid):
while j < hi and nums[i] > 2 * nums[j]: j += 1Both halves are sorted, so a larger nums[i] can only push j further right — it never moves back. Resetting makes the sweep O(n²) per merge instead of O(n).
Counting after sorting the range
nums[lo:hi] = sorted(nums[lo:hi]) # then count
# count across the two sorted halves nums[lo:hi] = sorted(nums[lo:hi])
Once the range is merged, the split between left and right is gone and you can no longer tell which element came from which half — only cross-half pairs count as reverse pairs. Count first, merge second.
Edge cases
2*nums[j] handles signs fine; comparisons stay valid on sorted halves.
2× a large int needs 64 bits; Python is safe.