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



   }
}