14. Count Reverse Pairs
β GFG solution to the Count Reverse Pairs problem: efficiently count pairs (i,j) where arr[i] > 2*arr[j] using modified merge sort technique. π
The problem can be found at the following link: π Question Link
π§© Problem Description
You are given an array arr[]
of positive integers. Your task is to find the count of reverse pairs. A pair of indices (i, j)
is said to be a reverse pair if both the following conditions are met:
0 β€ i < j < arr.size()
arr[i] > 2 * arr[j]
The goal is to efficiently count all such pairs in the given array.
π Examples
Example 1
Input: arr[] = [3, 2, 4, 5, 1, 20]
Output: 3
Explanation: The Reverse pairs are
(0, 4), arr[0] = 3, arr[4] = 1, 3 > 2*1
(2, 4), arr[2] = 4, arr[4] = 1, 4 > 2*1
(3, 4), arr[3] = 5, arr[4] = 1, 5 > 2*1
Example 2
Input: arr[] = [5, 4, 3, 2, 2]
Output: 2
Explanation: The Reverse pairs are
(0, 3), arr[0] = 5, arr[3] = 2, 5 > 2*2
(0, 4), arr[0] = 5, arr[4] = 2, 5 > 2*2
π Constraints
$1 \le \text{arr.size()} \le 5 \times 10^4$
$1 \le \text{arr}[i] \le 10^9$
β
My Approach
The optimal approach uses a Modified Merge Sort technique to efficiently count reverse pairs while maintaining the divide-and-conquer paradigm:
Modified Merge Sort Algorithm
Divide Phase:
Recursively divide the array into two halves until single elements remain.
Count reverse pairs in left half, right half, and cross-partition pairs.
Count Cross-Partition Pairs:
For each element in the left sorted subarray, count how many elements in the right sorted subarray satisfy the reverse pair condition.
Use two pointers technique: for each
arr[i]
in left half, find allarr[j]
in right half wherearr[i] > 2 * arr[j]
.
Merge Phase:
Merge the two sorted halves back into a single sorted array.
This ensures subsequent recursive calls work with sorted subarrays.
Optimization:
Since both halves are sorted, we can use the two-pointer technique efficiently.
Once we find the rightmost valid
j
for a giveni
, all elements fromm+1
toj
form valid pairs witharr[i]
.
π Time and Auxiliary Space Complexity
Expected Time Complexity: O(n log n), where n is the size of the array. The divide phase creates O(log n) levels, and each level performs O(n) work for counting pairs and merging.
Expected Auxiliary Space Complexity: O(n), as we use temporary arrays during the merge process and the recursion stack depth is O(log n).
π§βπ» Code (C++)
class Solution {
public:
int countRevPairs(vector<int>& arr) {
return mergeSort(arr, 0, arr.size() - 1);
}
private:
int mergeSort(vector<int>& arr, int l, int r) {
if (l >= r) return 0;
int m = l + (r - l) / 2;
return mergeSort(arr, l, m) + mergeSort(arr, m + 1, r) + merge(arr, l, m, r);
}
int merge(vector<int>& arr, int l, int m, int r) {
int cnt = 0, j = m + 1;
for (int i = l; i <= m; i++) {
while (j <= r && arr[i] > 2LL * arr[j]) j++;
cnt += j - m - 1;
}
vector<int> temp(r - l + 1);
int i = l, k = 0;
j = m + 1;
while (i <= m && j <= r) temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
while (i <= m) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
for (i = l; i <= r; i++) arr[i] = temp[i - l];
return cnt;
}
};
β Code (Java)
class Solution {
public int countRevPairs(int[] arr) {
return mergeSort(arr, 0, arr.length - 1);
}
private int mergeSort(int[] arr, int l, int r) {
if (l >= r) return 0;
int m = l + (r - l) / 2;
return mergeSort(arr, l, m) + mergeSort(arr, m + 1, r) + merge(arr, l, m, r);
}
private int merge(int[] arr, int l, int m, int r) {
int cnt = 0, j = m + 1;
for (int i = l; i <= m; i++) {
while (j <= r && arr[i] > 2L * arr[j]) j++;
cnt += j - m - 1;
}
int[] temp = new int[r - l + 1];
int i = l, k = 0;
j = m + 1;
while (i <= m && j <= r) temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
while (i <= m) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, l, temp.length);
return cnt;
}
}
π Code (Python)
class Solution:
def countRevPairs(self, arr):
def mergeSort(l, r):
if l >= r: return 0
m = (l + r) // 2
return mergeSort(l, m) + mergeSort(m + 1, r) + merge(l, m, r)
def merge(l, m, r):
cnt = j = 0
for i in range(l, m + 1):
while m + 1 + j <= r and arr[i] > 2 * arr[m + 1 + j]: j += 1
cnt += j
arr[l:r+1] = sorted(arr[l:r+1])
return cnt
return mergeSort(0, len(arr) - 1)
π§ Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: π¬ Any Questions?. Let's make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated