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`

, 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[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++;
}
}
}
```

## Discussion (0)