31. Reverse Pairs

Topic :

arrays

Difficulty :

hard

Problem Link :

link

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:

0 <= i < j < nums.length and
nums[i] > 2 * nums[j].

Example 1:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2:

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Constraints:

1 <= nums.length <= 5 * 104
-231 <= nums[i] <= 231 - 1

solution

import java.io.*;
import java.util.*;
 class Reverse_Pairs
{    
    static int merge(int nums[],int low, int mid, int high)
    {   
        int count=0;
        int j=mid+1;
        for(int i=low;i<=mid;i++)
        { 
            while(j<=high && nums[i]>(2*(long)nums[j])) // check for the condition for reverse pairs
            { j++;
            }
            count+=(j-(mid+1)); // no.of possible reverse pairs
        }
        
        ArrayList<Integer> temp=new ArrayList<>(); // temp array to store the elements
        
        // merging the sub arrays as in merge sort
        int left=low, right=mid+1;
        
        while(left<=mid && right<=high)
        { 
            if(nums[left]<=nums[right])
            {temp.add(nums[left++]);
            }
            else 
            {temp.add(nums[right++]);
            }
        }
        
        while(left<=mid)
        { temp.add(nums[left++]);
        }
        while(right<=high)
        {
           temp.add(nums[right++]);
        }
        
        for(int i=low;i<=high;i++)
        {nums[i]=temp.get(i-low);} // i-low is imp
        return count; 
    }
    static int mergeSort(int []nums, int low, int high)
    { if(low>=high)
       return 0;
       int mid=(low+high)/2;
       int inv= mergeSort(nums,low,mid); // no.of inversion in left half
       inv+=mergeSort(nums,mid+1,high);// no.of inversion in right half
       
       inv+=merge(nums,low,mid,high); // no.of inversion in complete left half and complete second half
       return inv;
    }
    
    static int reversePairs(int nums[])
    {
        return mergeSort(nums,0,nums.length-1);
    }
    public static void main(String args[])
    {int nums[]={2,4,3,5,1};
      System.out.println(reversePairs(nums));
     }
}