Given an integer array nums, return the number ofreverse pairsin the array. (link)

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

Solution

Brute force Approach

We check all the pairs and count the pairs which satisfy the condition

nums[i]> 2* nums[j] where i<j

Time - O(n^2)

Space - O(1)

class Solution {
    public int reversePairs(int[] nums) {
        int pairs = 0;
        for(int i=0; i<nums.length; i++){
            long a = nums[i];
            for(int j=i+1; j<nums.length;j++){
                long b = nums[j];
                if(a >  2 * b){
                    pairs+=1;
                }
            }
        }
        return pairs;
    }
}

Optimal Approach - Merge Sort

Before understanding this solution, go through the following algorithms

1. Merge Sort Algorithm (link)

2. Count inversions Algorithm (link)

The method of counting inversions encounters a limitation because it assumes that if the left element exceeds the right element, then it follows that all subsequent elements to the left are also greater than the right element. Consequently, during the merge process, we preserve the right element and advance the right pointer. While substituting the condition nums[i] > nums[j] with nums[i] > 2 * nums[j] during merging may appear initially correct, it proves problematic when the condition fails.

For instance, consider the arrays [6, 13, 21, 25] and [1, 2, 3, 4, 4, 5, 9, 11, 13]. When evaluating the condition 6 > 2 * 3, it evaluates to false, leading us to include the element 3 in the result while overlooking its potential pairings with 13, 21, and 25.

Thus, we opt not to incorporate this condition during the merging of the two sorted arrays. Instead, we conduct the counting of reverse pairs before merging, necessitating its separation.

The straightforward approach involves counting the pairs that satisfy the condition. To optimize this process, we make an important observation.

Upon examining the pairings:

• 6 can pair with 1, 2.

• 13 can pair with 1, 2, 3, 4, 4, 5.

• 21 can pair with 1, 2, 3, 4, 4, 5, 9.

• 25 can pair with 1, 2, 3, 4, 4, 5, 9, 11.

Consequently, the next element on the right can inherently pair with all the elements that the current element can pair with. For instance, 13 can pair with all the elements with which 6 could pair. Thus, the counting commences immediately after the point where the current element fails to satisfy the condition. In this case, 13 would start counting from 3 because 6 did not meet the condition.

It's important to exercise caution, particularly when negative elements are present, although the algorithm accommodates for such cases. Nonetheless, it's worth noting that if 'a' is a positive element, then (a, -a) constitutes a valid pair since a > 2 * (-a) holds true.

Example:[2147483647,2147483647,-2147483647,-2147483647,-2147483647,2147483647]

Time - O(2*n) * O(logn)

Space - O(n)

mergeSort takes O(logn)

merge of 2 sorted arrays takes O(n)

count reverse pairs takes O(n)

class Solution {
    public int mergeSort(int[] nums, int low, int high){
        if(low == high) return 0;

        int mid = (low + high) / 2;

        int ans = 0;

        ans += mergeSort(nums, low, mid);
        ans += mergeSort(nums, mid+1, high);
        ans += countReversePairs(nums, low, mid, high);
        merge(nums, low, mid, high);
        return ans;
    }

    public int countReversePairs(int[] nums, int low, int mid, int high){

        int ptr1 = low;
        int ptr2 = mid+1;
        int ans = 0;

        while(ptr1<=mid){
            while(ptr2<=high){
                long a = nums[ptr1];
                long b = nums[ptr2];

                if(a > 2 * b) {
                    ptr2+=1;
                    continue;
                }
                else{
                    break;
                }
            }
            ans += (ptr2-mid-1);
            ptr1+=1;
        }
        return ans;
    }

    public void merge(int[] nums, int low, int mid, int high){
        int length = high - low + 1;

        int[] dummy = new int[length];
        int index = 0;

        int ptr1 = low;
        int ptr2 = mid+1;

        while(ptr1<=mid && ptr2<=high){
            if(nums[ptr1]<=nums[ptr2]){
                dummy[index] = nums[ptr1];
                index+=1;
                ptr1+=1;
            }else{
                dummy[index] = nums[ptr2];
                index+=1;
                ptr2+=1;
            }
        } 

        while(ptr1<=mid){
            dummy[index] = nums[ptr1];
            index+=1;
            ptr1+=1;
        }
        while(ptr2<=high){
            dummy[index] = nums[ptr2];
            index+=1;
            ptr2+=1;        
        }

        for(int i=0; i<length; i++){
            nums[low+i] = dummy[i];
        }

    }


    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length-1);
        // for(int i=0; i<nums.length; i++)
        // System.out.print(nums[i]+ " ");
        // return 1;
    }
}