#493
Reverse Pairs
Hard Merge sort counting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count pairs (i, j) with i < j and nums[i] > 2 × nums[j].
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count pairs i < j with nums[i] > 2 × nums[j].
Why this works: inside merge sort both halves are sorted, so one pointer sweep counts pairs across the halves before merging.
Example: [1, 3, 2, 3, 1]
pairs: (3, 1) at indexes 1, 4 and (3, 1) at 3, 4answer 2
✦Hints open one at a time
Inside merge sort, both halves are sorted before the merge.
For each i in the left half, move a pointer j through the right half while nums[i] > 2·nums[j]. j never moves back.
Use long for 2 × nums[j].
↗Approach
In each merge step, first count pairs with a two-pointer sweep over the two sorted halves, then merge normally.
</>Solution (Java)
class Solution {
public int reversePairs(int[] nums) {
return sort(nums, new int[nums.length], 0, nums.length - 1);
}
private int sort(int[] a, int[] tmp, int lo, int hi) {
if (lo >= hi) return 0;
int mid = (lo + hi) >>> 1;
int count = sort(a, tmp, lo, mid) + sort(a, tmp, mid + 1, hi);
for (int i = lo, j = mid + 1; i <= mid; i++) {
while (j <= hi && a[i] > 2L * a[j]) j++; // j only moves forward
count += j - (mid + 1);
}
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
return count;
}
}!Common mistake
Computing 2 * nums[j] in int — values up to 2^31 overflow.
Complexity
- Time: O(n log n).
- Space: O(n).
Topic: Sorting
🎬 Episodes 24–28: video coming soon