Practice › Arrays
Reverse Pairs
Hard · Arrays · Asked at Google, Amazon, Microsoft, Uber
Count the pairs (i, j) with i < j and a[i] > 2 · a[j].
Input
First line: n. Second line: n space-separated integers.
Output
The number of reverse pairs.
Constraints
- 1 ≤ n ≤ 5 · 10^4
- -2^31 ≤ a[i] ≤ 2^31 − 1
Merge sort: before merging two sorted halves, count for each element of the left half how many right-half elements are less than half of it (two pointers). Use 64-bit arithmetic for 2·a[j].
Example 1
Input
5 1 3 2 3 1
Output
2
Example 2
Input
5 2 4 3 5 1
Output
3
Hints
- The O(n²) double loop is too slow for n = 5·10^4.
- During merge sort, both halves are sorted. For each left element, a pointer into the right half that only moves forward counts how many right elements satisfy a[i] > 2·a[j].
Approach
Modified merge sort, like counting inversions. In sort(l, r): sort both halves recursively, then — before merging — count cross pairs. Because both halves are sorted, as i moves right through the left half, the number of j in the right half with a[i] > 2·a[j] can only grow, so one pointer j sweeps the right half once. Then merge normally. Use 64-bit for 2·a[j] (values reach ±2^31).
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
vector<long long> a, tmp;
long long solve(int l, int r) {
if (r - l <= 1) return 0;
int m = (l + r) / 2;
long long cnt = solve(l, m) + solve(m, r);
int j = m;
for (int i = l; i < m; i++) {
while (j < r && a[i] > 2 * a[j]) j++;
cnt += j - m;
}
merge(a.begin() + l, a.begin() + m, a.begin() + m, a.begin() + r, tmp.begin() + l);
copy(tmp.begin() + l, tmp.begin() + r, a.begin() + l);
return cnt;
}
int main() {
int n;
cin >> n;
a.resize(n);
tmp.resize(n);
for (auto &x : a) cin >> x;
cout << solve(0, n) << "\n";
return 0;
}Python solution
import sys
def solve(a):
if len(a) <= 1:
return a, 0
m = len(a) // 2
left, c1 = solve(a[:m])
right, c2 = solve(a[m:])
cnt, j = c1 + c2, 0
for x in left:
while j < len(right) and x > 2 * right[j]:
j += 1
cnt += j
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged += left[i:] + right[j:]
return merged, cnt
data = list(map(int, sys.stdin.read().split()))
print(solve(data[1 : 1 + data[0]])[1])Java solution
import java.util.*;
import java.io.*;
public class Main {
static long[] a, tmp;
static long solve(int l, int r) {
if (r - l <= 1) return 0;
int m = (l + r) / 2;
long cnt = solve(l, m) + solve(m, r);
int j = m;
for (int i = l; i < m; i++) {
while (j < r && a[i] > 2 * a[j]) j++;
cnt += j - m;
}
int i = l, k = l;
j = m;
while (i < m && j < r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i < m) tmp[k++] = a[i++];
while (j < r) tmp[k++] = a[j++];
System.arraycopy(tmp, l, a, l, r - l);
return cnt;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
StringTokenizer st = new StringTokenizer(br.readLine());
a = new long[n];
tmp = new long[n];
for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
System.out.println(solve(0, n));
}
}