384. Reverse Pairs
Your function receives an integer array nums. A reverse pair is a pair of indices (i, j) with i < j such that nums[i] > 2 · nums[j] — the earlier element is more than twice the later one.
Return the total number of reverse pairs in the array, as a single integer.
Values span the full 32-bit range, so 2 · nums[j] can overflow a 32-bit integer — compute with 64-bit arithmetic.
Example 1:
Input: nums = [1, 3, 2, 3, 1]
Output: 2
Explanation: The qualifying pairs are (1, 4) since 3 > 2 · 1, and (3, 4) since 3 > 2 · 1. No other pair has its left element more than twice its right element.
Example 2:
Input: nums = [2, 4, 3, 5, 1]
Output: 3
Explanation: The pairs (1, 4), (2, 4) and (3, 4) all compare against nums[4] = 1: 4 > 2, 3 > 2 and 5 > 2. Note (0, 4) fails because 2 > 2 is false — the inequality is strict.
Constraints:
- 1 ≤ nums.length ≤ 5 · 10⁴
- -2³¹ ≤ nums[i] ≤ 2³¹ - 1
- The answer fits in a 64-bit integer
Hints:
Brute force compares every pair — O(n²), too slow at 5 · 10^4 elements. Ask: if the left half and right half of the array were each sorted, could you count the pairs that straddle the middle faster?
Piggyback on merge sort. Just before merging two sorted halves, walk a pointer j across the right half once per level: as the left element grows, the set of right elements it beats only grows too, so j never moves backward. Count with 64-bit math — 2 · nums[j] overflows 32 bits.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 3, 2, 3, 1]
Expected output: 2