Divide & Conquer — Reverse Pairs
↗ LeetCode: Reverse Pairs · Hard · pattern chapter →
Asked atGoogleAmazon
Count pairs (i, j) with i < j and nums[i] > 2 · nums[j].
Example 1 — nums=[1,3,2,3,1] → 2Example 2 — nums=[2,4,3,5,1] → 3
Constraints — 1 ≤ n ≤ 5·10⁴; -2³¹ ≤ nums[i] ≤ 2³¹−1. Brute nested-loop pair check is O(n²) = 2.5·10⁹ ops at n=5·10⁴ (TLE). Merge-sort D&C or BIT with coord compression is O(n log n) = ~10⁶ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — All pairs
O(n²). TLE.
Approach 2 — Merge sort with reverse-pair counting (canonical)
Insight. During merge sort, before merging two sorted halves, count pairs (i, j) with i in left, j in right, and nums[i] > 2 · nums[j]. Use two pointers on the two sorted halves.
Trap — use long for 2 * nums[j] to avoid overflow.
java
int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length - 1);
}
int mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return 0;
int mid = (lo + hi) / 2;
int count = mergeSort(a, lo, mid) + mergeSort(a, mid + 1, hi);
int j = mid + 1;
for (int i = lo; i <= mid; i++) {
while (j <= hi && a[i] > 2L * a[j]) j++;
count += j - mid - 1;
}
int[] merged = new int[hi - lo + 1];
int p = lo, q = mid + 1, w = 0;
while (p <= mid && q <= hi) merged[w++] = a[p] <= a[q] ? a[p++] : a[q++];
while (p <= mid) merged[w++] = a[p++];
while (q <= hi) merged[w++] = a[q++];
System.arraycopy(merged, 0, a, lo, merged.length);
return count;
}Execution Trace
Complexity — Time O(n log n); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| All pairs | O(n²) | O(1) | baseline |
| Merge sort count | O(n log n) | O(n) | canonical |
When to use which
- Standard inversion / reverse pair counting → merge sort.
- BIT alternative → compress values; sweep left-to-right; BIT counts smaller / larger.
- k times threshold → same skeleton with different pointer logic.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems