Reverse Pairs — Solution in Python, Java & C++
Reverse Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Reverse Pairs is a hard coding problem on arrays, binary search and divide and conquer, asked in Amazon, Google, Meta and Intuit interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Divide and Conquer, Binary Indexed Tree, Merge Sort
- Asked at: Amazon, Google, Meta, Intuit
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A reverse pair is a pair of indices i < j with nums[i] > 2 · nums[j].
Return the number of reverse pairs in nums.
Example 1
Input: nums = [1,3,2,3,1]
Output: 2
Explanation: `(1,4)` with 3 > 2 and `(3,4)` with 3 > 2.
Example 2
Input: nums = [2,4,3,5,1]
Output: 3
Explanation: `(1,4)`, `(2,4)` and `(3,4)`.
Example 3
Input: nums = [5,4,3,2,1]
Output: 4
Constraints
1 <= nums.length <= 5 * 10^4-10^9 <= nums[i] <= 10^9
Hints for Reverse Pairs
Hint 1
The quadratic scan is too slow — the pairs have to be counted during a divide and conquer.
Hint 2
Inside a merge sort, count the pairs whose left index is in the left half and right index in the right half.
Hint 3
Because both halves are already sorted, that count is a single forward sweep before the merge.
How to solve Reverse Pairs
Merge sort with a counting step. After both halves are sorted, count the cross pairs i in the left, j in the right with nums[i] > 2 · nums[j]; because both halves are sorted, a single pointer over the right half suffices. Then merge and return the total.
Approach
- Recurse on
[lo, mid)and[mid, hi), summing their counts. - Sweep
iacross the left half, advancingjin the right half whilework[i] > 2 · work[j]; addj - midfor eachi. - Merge the two halves back into sorted order.
Why it works
The counting sweep is linear rather than quadratic because both halves are sorted: as i moves right its value grows, so the threshold j only ever moves right too — it never backtracks. Counting before the merge is essential, since the merge destroys the separation between the halves that the pair definition relies on.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
2 · nums[j]overflows a 32-bit integer at the upstream bounds — the comparison needs 64-bit arithmetic there.- The count must be taken before merging the halves.
- The
jpointer is shared across the whole sweep; resetting it perimakes the step quadratic again.
Reference solution
Python
from typing import List
def reversePairs(nums: List[int]) -> int:
work = nums[:]
def sort_count(lo: int, hi: int) -> int:
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
total = sort_count(lo, mid) + sort_count(mid, hi)
j = mid
for i in range(lo, mid):
while j < hi and work[i] > 2 * work[j]:
j += 1
total += j - mid
work[lo:hi] = sorted(work[lo:hi])
return total
return sort_count(0, len(work))Java
public static int reversePairs(int[] nums) {
int[] work = nums.clone();
int[] buffer = new int[work.length];
return rpSortCount(work, buffer, 0, work.length);
}
private static int rpSortCount(int[] work, int[] buffer, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) >>> 1;
int total = rpSortCount(work, buffer, lo, mid) + rpSortCount(work, buffer, mid, hi);
int j = mid;
for (int i = lo; i < mid; i++) {
while (j < hi && (long) work[i] > 2L * work[j]) j++;
total += j - mid;
}
int a = lo, b = mid, w = lo;
while (a < mid || b < hi) {
if (b >= hi || (a < mid && work[a] <= work[b])) buffer[w++] = work[a++];
else buffer[w++] = work[b++];
}
for (int i = lo; i < hi; i++) work[i] = buffer[i];
return total;
}C++
static int rpSortCount(vector<int>& work, vector<int>& buffer, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) / 2;
int total = rpSortCount(work, buffer, lo, mid) + rpSortCount(work, buffer, mid, hi);
int j = mid;
for (int i = lo; i < mid; i++) {
while (j < hi && (long long) work[i] > 2LL * work[j]) j++;
total += j - mid;
}
int a = lo, b = mid, w = lo;
while (a < mid || b < hi) {
if (b >= hi || (a < mid && work[a] <= work[b])) buffer[w++] = work[a++];
else buffer[w++] = work[b++];
}
for (int i = lo; i < hi; i++) work[i] = buffer[i];
return total;
}
int reversePairs(vector<int>& nums) {
vector<int> work = nums;
vector<int> buffer(work.size(), 0);
return rpSortCount(work, buffer, 0, (int) work.size());
}JavaScript
var reversePairs = function(nums) {
var work = nums.slice();
var buffer = [];
for (var t = 0; t < work.length; t++) buffer.push(0);
var sortCount = function(lo, hi) {
if (hi - lo <= 1) return 0;
var mid = (lo + hi) >> 1;
var total = sortCount(lo, mid) + sortCount(mid, hi);
var j = mid, i;
for (i = lo; i < mid; i++) {
while (j < hi && work[i] > 2 * work[j]) j++;
total += j - mid;
}
var a = lo, b = mid, w = lo;
while (a < mid || b < hi) {
if (b >= hi || (a < mid && work[a] <= work[b])) buffer[w++] = work[a++];
else buffer[w++] = work[b++];
}
for (i = lo; i < hi; i++) work[i] = buffer[i];
return total;
};
return sortCount(0, work.length);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search