Problem Statement :-
Given an integer array nums
, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where :-
i < j
nums[i] > 2 * nums[j].
Example
Input : nums = [1,3,2,3,1]
Result : 2
Solution 1
this problem can be solved by Merge Sort algorithms.
in the Merge Sort, before merging two sorted sub-arrays we can linearly count the reverse pairs.
step-1 initialise two variables
i = left
initial index of subArr1
k = mid + 1
intial index of subArr2
step-2 run a loop from i=0 to subArr1.length,
1. keep increasing
k
, whilesubArr1[i] > subArr2[k] * 2
2. if above condition not satisfy then addk
toans
example:- subArr1 = [5,7,8]
subArr2 = [1,4,4]
ans = 0
subArr1 = [5,7,8] subArr2 = [1,4,4]
i k
5 > 1*2 --> increase k++ k = 1
ans = 0
subArr1 = [5,7,8] subArr2 = [1,4,4]
i k
5 > 4*2 --> it doesn't satisfy the condition then add k to ans
ans += k
ans = 1
subArr1 = [5,7,8] subArr2 = [1,4,4]
i k
7 > 4*2 --> it doesn't satisfy the condition then add k to ans
ans += k
ans = 2
subArr1 = [5,7,8] subArr2 = [1,4,4]
i k
8 > 4*2 --> it doesn't satisfy the condition then add k to ans
ans += k
we will stop,bcoz i goes out of boundary.
we found ans = 3
reverse pairs from sub arrays.
Java
class Solution {
public int reversePairs(int[] nums) {
int[] ans = new int[1];
mergeSort(nums,0,nums.length-1,ans);
return ans[0];
}
private static void mergeSort(int[] arr,int left,int right,int[] ans){
if(left >= right) return;
int mid = ( left + right ) / 2;
mergeSort(arr,left,mid,ans);
mergeSort(arr,mid+1,right,ans);
merge(arr,left,mid,right,ans);
}
private static void merge(int[] arr,int left,int mid,int right,int[] ans){
int leftArrSize = mid - left+1;
int rightArrSize = right - mid;
int[] leftArr = new int[leftArrSize];
int[] rightArr = new int[rightArrSize];
// count the reverse pairs
int k = mid + 1;
for(int i = left;i<=mid;i++) {
while(k<=right && arr[i] > (2 * (long) arr[k])) {
k++;
}
ans[0] += (k - (mid+1));
}
for (int i = 0; i < leftArrSize; ++i)
leftArr[i] = arr[left + i];
for (int j = 0; j < rightArrSize; ++j)
rightArr[j] = arr[mid + 1 + j];
int leftPointer = 0;
int rightPointer = 0;
int arrPointer = left;
while(leftPointer < leftArrSize && rightPointer < rightArrSize ){
if(leftArr[leftPointer] <= rightArr[rightPointer]){
arr[arrPointer] = leftArr[leftPointer];
arrPointer++;
leftPointer++;
}else{
arr[arrPointer] = rightArr[rightPointer];
arrPointer++;
rightPointer++;
}
}
while(leftPointer < leftArrSize){
arr[arrPointer] = leftArr[leftPointer];
arrPointer++;
leftPointer++;
}
while(rightPointer < rightArrSize){
arr[arrPointer] = rightArr[rightPointer];
arrPointer++;
rightPointer++;
}
}
}
Top comments (0)