Striver's SDE Sheet Journey - #18 Count Reverse Pairs
Tags: programming, beginners, java, tutorial
Published: 2022-01-25 10:21:18

> **<u>Problem Statement</u> :-**

_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`

##  <u>Solution 1</u>
_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

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



   }
}
```