Problem Statement
Given an integer array nums. Return the number of reverse pairs in the array.
An index pair (i, j) is called a reverse pair if:
- 0 <= i < j < nums.length
- nums[i] > 2 * nums[j].
LeetCode:
Constraints:
1 <= nums.length <= 5 * 10^4
-2^31 <= nums[i] <= 2^31 - 11 ≤ nums.length ≤ 5*10^4- The input array will have at least 1 element.
- At most, it can have
50,000elements. - Any algorithm worse than
O(n log n)(likeO(n^2)) might time out for large inputs, so you need an efficient approach.
-2^31 ≤ nums[i] ≤ 2^31 - 1- This referes to the value range of each element in the array:
- The minimum possible value is:
-2^31 = -2147483648.2^31 - 1 = 2147483647.
- These are limits of a 32-bit signed integer.
If you ever do operations like
2 * nums[i], there is a risk of integer overflow because:int x = 1e9; int y = 2 * x; // = 2e9, still OK int z = 2 * INT_MAX; // OVERFLOW
- The minimum possible value is:
- This referes to the value range of each element in the array:
Examples
Example: 1
Input: nums = [6, 4, 1, 2, 7]
Output: 3
Explanation:
The reverse pairs are:
(0, 2): nums[0] = 6, nums[2] = 1, 6 > 2 * 1
(0, 3): nums[0] = 6, nums[3] = 2, 6 > 2 * 2
(1, 2): nums[1] = 4, nums[2] = 1, 4 > 2 * 1Example: 2
Input: nums = [5, 4, 4, 3, 3]
Output: 0
Explanation:
No pairs satisfy both the conditions.Example: 3
Input: nums = [6, 4, 4, 2, 2]
Output: 2
Explanation:
The reverse pairs are:
(0, 3): nums[0] = 6, nums[3] = 2, 6 > 2 * 2
(0, 3): nums[0] = 6, nums[4] = 2, 6 > 2 * 2Different Approaches
1️⃣ Brute Force Approach
Intuition:
The straightforward approach to solve this problem is to iterate through each element in the array and run an inner loop say(j) to check all subsequent elements arr[j], if the condition arr[i] > 2 x arr[j] holds true, where i is the parent loop, then it is a reverse pair otherwise it's not a reverse pair.
Approach:
- Iterate in the array from
0toN-1to select the arr[i]. As index j should be greater than index i, inside loop i, run another loop i.e. j from i+1 to N-1, and select the element arr[j]. - Inside this second loop, check if arr[i] is greater than 2*arr[j] i.e. if arr[i] and arr[j] can be a pair. If they satisfy the condition, increase the count by 1. Finally, return the count as our answer.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to count reverse
pairs where a[i] > 2 * a[j]*/
int reversePairs(vector<int>& nums) {
// Call countPairs with the vector and its size
return countPairs(nums, nums.size());
}
private:
/* Helper function to count pairs
satisfying the condition a[i] > 2 * a[j]*/
int countPairs(vector<int>& nums, int n) {
// Initialize count of reverse pairs
int cnt = 0;
/* Nested loops to check each
pair (i, j) where i < j*/
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
/* Check if the condition
a[i] > 2 * a[j] holds*/
if (nums[i] > 2 * nums[j]) {
/* Increment count if
condition is satisfied*/
cnt++;
}
}
}
// Return the total count of reverse pairs
return cnt;
}
};
int main() {
vector<int> nums = {6, 4, 1, 2, 7};
// Create an instance of the Solution class
Solution sol;
int cnt = sol.reversePairs(nums);
// Output the result
cout << "The number of reverse pairs is: " << cnt << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N^2), whereNis size of the given array. For using nested loops here and those two loops roughly run forNtimes. - Space Complexity:
O(1), no extra space is used to solve this problem.
2️⃣ Modified Merge Sort
Intuition:
In order to solve this problem in optimal way, use the concept of modified merge sort. Here, the approach will be to check, for every element in the sorted left, how many elements in the right half (also sorted) can make pair.
Let's understand:
+-----+-----+-----+-----+
arr1 = | 6 | 13 | 21 | 25 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+-----+
arr2 = | 1 | 2 | 3 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
j
Here, the checking ends at j = 2,
as 6 = 2 * 3For the first element of the left half i.e. 6, start checking from index 0 of the right half i.e. arr2[]. Now, we can clearly see that the first two elements of arr2[] can make a pair with arr1[0] i.e. 6.
+-----+-----+-----+-----+
arr1 = | 6 | 13 | 21 | 25 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
+-----+-----+-----+-----+-----+-----+
arr2 = | 1 | 2 | 3 | 4 | 4 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
j
For element 13 we will start checking
from this index.This process will work because arr1[1] will always be greater than arr1[0] which concludes if arr2[0] and arr2[1] are making a pair with arr1[0], they will obviously make pairs with a number greater than arr1[0] i.e. arr1[1].
Thus before the merge step in the merge sort algorithm, calculate the total number of pairs each time.
Code:
/*
Time Complexity : O(NlogN), Each recursive call to performs two recursive calls on subslices of size N/2 and
One linear scans of length <= N. Therefore, the time complexity of the divide & conquer approach can be
represented by the following recurrence relation: T(N)=2T(N/2)+N. Where N is the size of the Array(nums).
Space Complexity : O(N), Recursion Stack Space O(logN) + Array(temp) space O(N).
Solved using Array + Divide and Conquer + Merge Sort. Optimized Approach.
*/
/************* Approach 2 *****************/
class Solution {
private:
void merge(vector<int>& nums, int low, int mid, int high, int& reversePairsCount){
int j = mid+1;
for(int i=low; i<=mid; i++){
while(j<=high && nums[i] > 2*(long long)nums[j]){
j++;
}
reversePairsCount += j-(mid+1);
}
int size = high-low+1;
vector<int> temp(size, 0);
int left = low, right = mid+1, k=0;
while(left<=mid && right<=high){
if(nums[left] < nums[right]){
temp[k++] = nums[left++];
}
else{
temp[k++] = nums[right++];
}
}
while(left<=mid){
temp[k++] = nums[left++];
}
while(right<=high){
temp[k++] = nums[right++];
}
int m=0;
for(int i=low; i<=high; i++){
nums[i] = temp[m++];
}
}
void mergeSort(vector<int>& nums, int low, int high, int& reversePairsCount){
if(low >= high){
return;
}
int mid = (low + high) >> 1;
mergeSort(nums, low, mid, reversePairsCount);
mergeSort(nums, mid+1, high, reversePairsCount);
merge(nums, low, mid, high, reversePairsCount);
}
public:
int reversePairs(vector<int>& nums) {
int reversePairsCount = 0;
mergeSort(nums, 0, nums.size()-1, reversePairsCount);
return reversePairsCount;
}
};#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to count reverse
pairs where a[i] > 2 * a[j]*/
int reversePairs(vector<int>& nums) {
int n = nums.size();
return team(nums, n);
}
private:
/* Merge function to merge two
sorted halves and count reverse pairs*/
void merge(vector<int>& arr, int low, int mid, int high) {
// temporary array
vector<int> temp;
// starting index of left half of arr
int left = low;
// starting index of right half of arr
int right = mid + 1;
// Merge and count reverse pairs
while (left <= mid && right <= high) {
if (arr[left] <= arr[right]) {
temp.push_back(arr[left]);
left++;
}
else {
temp.push_back(arr[right]);
right++;
}
}
// Copy remaining elements from left half
while (left <= mid) {
temp.push_back(arr[left]);
left++;
}
// Copy remaining elements from right half
while (right <= high) {
temp.push_back(arr[right]);
right++;
}
// Transfer sorted elements from temp to arr
for (int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
}
private:
//Function to count reverse pairs
int countPairs(vector<int> &arr, int low, int mid, int high) {
int right = mid + 1;
int cnt = 0;
for (int i = low; i <= mid; i++) {
/*while right is less than equal to high
and arr[i] is greater than 2 * arr[right]
then increment right by 1*/
while (right <= high && arr[i] > 2 * arr[right]) right++;
cnt += (right - (mid + 1));
}
//Return the count
return cnt;
}
private:
/* Merge sort function to sort the
array and count reverse pairs*/
int mergeSort(vector<int>& arr, int low, int high) {
int cnt = 0;
if(low >= high){
return cnt;
}
int mid = low + (high - low) / 2;
// Sort left half
cnt += mergeSort(arr, low, mid);
// Sort right half
cnt += mergeSort(arr, mid + 1, high);
cnt += countPairs(arr, low, mid, high);
// Merge and count pairs
merge(arr, low, mid, high);
//Return the count of reverse pairs
return cnt;
}
private:
int team(vector <int> & skill, int n){
return mergeSort(skill, 0, n - 1);
}
};
int main() {
vector<int> nums = {6, 4, 1, 2, 7};
//Create an instance of Solution class
Solution sol;
int cnt = sol.reversePairs(nums);
//Print the count of reverse pairs
cout << "The number of reverse pairs is: " << cnt << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(2N * logN), where N is size of the given array.- Inside the mergeSort() we call merge() and countPairs() except mergeSort() itself. Now, inside the function countPairs(), though we are running a nested loop, we are actually iterating the left half once and the right half once in total.
- That is why, the time complexity is O(N). And the merge() function also takes O(N). The mergeSort() takes O(logN) time complexity. Therefore, the overall time complexity will be O(logN x (N+N)) = O(2NxlogN)
- Space Complexity:
O(N), as in the merge sort, a temporary array to store elements in sorted order is used.