## DEV Community is a community of 890,377 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Striver's SDE Sheet Journey - #18 Count Reverse Pairs

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 :-

1. `i < j`

2. `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` , while `subArr1[i] > subArr2[k] * 2`
2. if above condition not satisfy then add `k` to `ans`

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;

mergeSort(nums,0,nums.length-1,ans);

return ans;
}

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 += (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++;
}

}
}
``````