#493 Reverse Pairs
the problem
In plain words
Count pairs (i, j) with i < j and nums[i] > 2 · nums[j].
in nums = [1,3,2,3,1]
out 2
(1,4): 3 > 2·1 and (3,4): 3 > 2·1.
in nums = [2,4,3,5,1]
out 3
- 1 ≤ n ≤ 5·10⁴
- -2³¹ ≤ nums[i] ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMerge sort & merging sorted runsDivide and conquer
During merge sort, every pair (i in left half, j in right half) still has i < j in the original array. With both halves sorted, one forward-only pointer counts all cross pairs in O(n).
solutions
From brute force to optimal
Two loops, compare with long arithmetic.
- For i < j: if (long) nums[i] > 2L · nums[j], count++.
n(n−1)/2 pairs — ~1.25·10⁹ at the max n. TLE.
A counter.
class Solution { public int reversePairs(int[] nums) { int count = 0; for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++) if ((long) nums[i] > 2L * nums[j]) count++; // long: 2 * nums[j] overflows int return count; }}Count cross pairs between the two sorted halves, then merge as usual.
- Recursively count (and sort) both halves.
- j starts at mid+1; for each i in the left half advance j while a[i] > 2·a[j]; add j − (mid+1).
- Merge the halves so the parent gets a sorted range.
Each level does an O(n) count (j only moves forward) and an O(n) merge.
Copy of nums plus the helper array.
class Solution { public int reversePairs(int[] nums) { int[] a = nums.clone(); return sortAndCount(a, new int[a.length], 0, a.length - 1); } private int sortAndCount(int[] a, int[] aux, int lo, int hi) { if (lo >= hi) return 0; int mid = lo + (hi - lo) / 2; int count = sortAndCount(a, aux, lo, mid) + sortAndCount(a, aux, mid + 1, hi); // Both halves are sorted: count cross pairs with one forward-moving pointer. int j = mid + 1; for (int i = lo; i <= mid; i++) { while (j <= hi && (long) a[i] > 2L * a[j]) j++; count += j - (mid + 1); // a[mid+1..j-1] all satisfy a[i] > 2·a[j] } merge(a, aux, lo, mid, hi); // standard merge so the parent sees a sorted range return count; } private void merge(int[] a, int[] aux, int lo, int mid, int hi) { for (int k = lo; k <= hi; k++) aux[k] = a[k]; int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (aux[j] < aux[i]) a[k] = aux[j++]; else a[k] = aux[i++]; } }}in the room
How to say it in the interview
talk track
- Relate it to counting inversions: "merge sort sees every i < j pair exactly once across levels."
- Stress the overflow: 2 · nums[j] needs
long. - Explain why counting is separate from merging — the conditions differ (2× vs plain <).
traps
2 * nums[j]in int overflows for values near 2³¹.- Trying to count inside the merge loop — the 2× condition doesn't line up with merge order.
what they ask next
Follow-ups
Count of Smaller Numbers After Self (LC 315)?
Same idea: merge sort an index array and, when taking from the left half, add how many right-half elements were already taken.
Another O(n log n) approach?
A Fenwick tree (BIT) over compressed values, scanning right to left.
before you submit
Edge cases to test
- Values near ±2³¹:
2 * nums[j]overflows an int — compare aslong. - Negatives: −5 > 2 · (−5) = −10, so [−5, −5] has one pair.
- Equal non-negative values never pair up: x > 2x is false when x ≥ 0.
practise next
Similar problems
- #315Count of Smaller Numbers After SelfHardin Range Queries & Strings
- #912Sort an ArrayMediumin Sorting