Author at SyntaxFlow
Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair of indices (i, j) such that:
0 <= i < j < nums.lengthnums[i] > 2 * nums[j]Your task is to count all such reverse pairs efficiently.
nums = [1,3,2,3,1]
2
The reverse pairs are:
(3,1) → 3 > 2 × 1
(3,1) → 3 > 2 × 1
Therefore, the total number of reverse pairs is 2.
nums = [2,4,3,5,1]
3
The reverse pairs are:
(4,1) → 4 > 2 × 1
(3,1) → 3 > 2 × 1
(5,1) → 5 > 2 × 1
Hence, the answer is 3.
The simplest approach is to check every possible pair (i, j) where i < j.
If:
nums[i] > 2 * nums[j]
then it is a reverse pair, so increment the count.
class Solution {
public:
int reversePairs(vector<int>& nums) {
int count = 0;
int n = nums.size();
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if((long long)nums[i] > 2LL * nums[j]) {
count++;
}
}
}
return count;
}
};nums = [1,3,2,3,1]
O(n²)O(1)For:
n = 50,000
the number of comparisons is approximately:
n² = 50,000 × 50,000 = 2.5 billion
which is too slow.
That's why we use the Merge Sort based O(n log n) solution.
prerequisite:
merge sort
The brute-force solution checks every pair, resulting in O(n²) time.
To optimize, we use Merge Sort.
During Merge Sort, the left half and right half are already sorted.
Suppose:
Left = [1, 4, 5]
Right = [1, 2]
For each element in the left half, we want to count how many elements in the right half satisfy:
arr[i] > 2LL * arr[j]
Since the right half is sorted, once a j satisfies the condition, all previous valid j's are also counted. We can use a moving pointer and count efficiently.
class Solution {
public:
int merge(vector<int>& arr, int low, int mid, int high) {
vector<int> temp;
int left = low;
int right = mid + 1;
while(left <= mid && right <= high) {
if(arr[left] <= arr[right]) {
temp.push_back(arr[left++]);
} else {
temp.push_back(arr[right++]);
}
}
while(left <= mid) temp.push_back(arr[left++]);
while(right <= high) temp.push_back(arr[right++]);
for(int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
return 0;
}
int countPairs(vector<int>& arr, int low, int mid, int high) {
int right = mid + 1;
int count = 0;
for(int i = low; i <= mid; i++) {
while(right <= high &&
arr[i] > 2LL * arr[right]) {
right++;
}
count += (right - (mid + 1));
}
return count;
}
int mergeSort(vector<int>& arr, int low, int high) {
if(low >= high) return 0;
int mid = low + (high - low) / 2;
int count = 0;
count += mergeSort(arr, low, mid);
count += mergeSort(arr, mid + 1, high);
count += countPairs(arr, low, mid, high);
merge(arr, low, mid, high);
return count;
}
int reversePairs(vector<int>& nums) {
return mergeSort(nums, 0, nums.size() - 1);
}
};O(n log n)O(n)problem link:
video reference link: