Reverse Pairs hard
Description
Given nums, count the reverse pairs: pairs (i, j) where i < j and nums[i] > 2 * nums[j].
Examples
> nums = [1, 3, 2, 3, 1]
Output: 2
# (1,4): 3 > 2*1 ; (3,4): 3 > 2*1
> nums = [2, 4, 3, 5, 1]
Output: 3Constraints
1 <= nums.length <= 5 × 10^4-2^31 <= nums[i] <= 2^31 − 1(use 64-bit when doubling!)
Intuition
A counting-with-condition problem, like Count of Smaller, but the condition is nums[i] > 2 * nums[j]. Process left to right, keeping a value-indexed BIT of the elements seen so far (all have i < j relative to the current j). For each new nums[j], count how many already-seen values exceed 2 * nums[j] — those are the reverse pairs ending at j.
The wrinkle: we query by the value 2 * nums[j], which may not be one of the array’s values, so we compress both the original values and the doubled query thresholds together.
Code
Two traps specific to this problem: (1) overflow — 2 * nums[j] can exceed 32 bits, so compute it in 64-bit (2LL * x / Python is fine). (2) Compress the doubled thresholds too — the query value 2 * nums[j] is rarely itself an array element, so it must be part of the coordinate-compression set, or rank() will miss it. Forgetting either gives wrong counts on adversarial inputs.
Analysis
- Time: O(n log n) — compression sort plus n BIT operations.
- Space: O(n).
Like Count of Smaller, this also has an elegant merge-sort solution: count cross-pairs with
nums[i] > 2 * nums[j]during the merge. Same O(n log n). Mention both — interviewers often want to hear you know the BIT and the D&C framing.
Same skin
- Count of Smaller Numbers After Self — the same value-indexed BIT, simpler condition.
- Count of Range Sum — BIT over prefix sums, “how many prefix sums fall in a range.”
- Divide & Conquer counting (Day 26) — the merge-sort approach to inversion-style counting.