Reverse Pairs

Intuition

The straightforward approach to solve this problem is to iterate through each element in the array and run an inner loop say(j) to check all subsequent elements arr[j], if the condition arr[i] > 2 x arr[j] holds true, where i is the parent loop, then it is a reverse pair otherwise it's not a reverse pair.

Approach

iterate in the array from 0 to N-1 to select the arr[i]. As index j should be greater than index i, inside loop i, run another loop i.e. j from i+1 to N-1, and select the element arr[j].

Inside this second loop, check if arr[i] is greater than 2*arr[j] i.e. if arr[i] and arr[j] can be a pair. If they satisfy the condition, increase the count by 1. Finally, return the count as our answer.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to count reverse
    pairs where a[i] > 2 * a[j]*/
    int reversePairs(vector<int>& nums) {
        
        // Call countPairs with the vector and its size
        return countPairs(nums, nums.size()); 
        
    }

private:
    /* Helper function to count pairs
    satisfying the condition a[i] > 2 * a[j]*/
    int countPairs(vector<int>& nums, int n) {
        
        // Initialize count of reverse pairs
        int cnt = 0;
        
        /* Nested loops to check each
        pair (i, j) where i < j*/
        for (int i = 0; i < n; i++) {
            
            for (int j = i + 1; j < n; j++) {
                
                /* Check if the condition 
                a[i] > 2 * a[j] holds*/
                if (nums[i] > 2 * nums[j]) {
                    
                    /* Increment count if
                    condition is satisfied*/
                    cnt++; 
                    
                }
            }
        }
        // Return the total count of reverse pairs
        return cnt; 
    }
};

int main() {
    
    vector<int> nums = {6, 4, 1, 2, 7}; 
    
    // Create an instance of the Solution class
    Solution sol; 
    
    int cnt = sol.reversePairs(nums); 
    
    // Output the result
    cout << "The number of reverse pairs is: " << cnt << endl;
    return 0; 
}
import java.util.*;

class Solution {
    /* Function to count reverse
    pairs where a[i] > 2 * a[j]*/
    public int reversePairs(int[] nums) {
        
        // Call countPairs with the array and its length
        return countPairs(nums, nums.length); 
        
    }

    /* Helper function to count pairs
    satisfying the condition a[i] > 2 * a[j]*/
    private int countPairs(int[] nums, int n) {
        
        // Initialize count of reverse pairs
        int cnt = 0;
        
        /* Nested loops to check each
        pair (i, j) where i < j*/
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                
                /* Check if the condition 
                a[i] > 2 * a[j] holds*/
                if (nums[i] > 2 * nums[j]) {
                    
                    /* Increment count if
                    condition is satisfied*/
                    cnt++; 
                    
                }
            }
        }
        // Return the total count of reverse pairs
        return cnt; 
    }

    public static void main(String[] args) {
        
        int[] nums = {6, 4, 1, 2, 7}; 
        
        // Create an instance of the Solution class
        Solution sol = new Solution(); 
        
        int cnt = sol.reversePairs(nums); 
        
        // Output the result
        System.out.println("The number of reverse pairs is: " + cnt);
    }
}
from typing import List

class Solution:
    """ Function to count reverse
    pairs where a[i] > 2 * a[j]"""
    def reversePairs(self, nums: List[int]) -> int:
        
        # Call countPairs with the list and its length
        return self.countPairs(nums, len(nums))
    
    """ Helper function to count pairs
    satisfying the condition a[i] > 2 * a[j]"""
    def countPairs(self, nums: List[int], n: int) -> int:
        
        # Initialize count of reverse pairs
        cnt = 0
        
        """ Nested loops to check each
        pair (i, j) where i < j"""
        for i in range(n):
            for j in range(i + 1, n):
                
                """ Check if the condition 
                a[i] > 2 * a[j] holds"""
                if nums[i] > 2 * nums[j]:
                    
                    """ Increment count if
                    condition is satisfied"""
                    cnt += 1
                    
        # Return the total count of reverse pairs
        return cnt

if __name__ == "__main__":
    nums = [6, 4, 1, 2, 7]
    
    # Create an instance of the Solution class
    sol = Solution()
    
    cnt = sol.reversePairs(nums)
    
    # Output the result
    print("The number of reverse pairs is:", cnt)
class Solution {
    /* Function to count reverse
    pairs where a[i] > 2 * a[j]*/
    reversePairs(nums) {
        
        // Call countPairs with the array and its length
        return this.countPairs(nums, nums.length); 
        
    }

    /* Helper function to count pairs
    satisfying the condition a[i] > 2 * a[j]*/
    countPairs(nums, n) {
        
        // Initialize count of reverse pairs
        let cnt = 0;
        
        /* Nested loops to check each
        pair (i, j) where i < j*/
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                
                /* Check if the condition 
                a[i] > 2 * a[j] holds*/
                if (nums[i] > 2 * nums[j]) {
                    
                    /* Increment count if
                    condition is satisfied*/
                    cnt++; 
                }
            }
        }
        // Return the total count of reverse pairs
        return cnt; 
    }
}


const nums = [6, 4, 1, 2, 7];

// Create an instance of the Solution class
const sol = new Solution(); 

const cnt = sol.reversePairs(nums); 

// Output the result
console.log("The number of reverse pairs is: " + cnt);

Complexity Analysis

Time Complexity: O(N²), where N is size of the given array. For using nested loops here and those two loops roughly run for N times.

Space Complexity: O(1), no extra space is used to solve this problem.

Intuition

In order to solve this problem in optimal way, use the concept of modified merge sort. Here, the approach will be to check, for every element in the sorted left half, how many elements in the right half(also sorted) can make a pair. Let’s try to understand, using the following example:

For the first element of the left half i.e. 6, start checking from index 0 of the right half i.e. arr2[]. Now, we can clearly see that the first two elements of arr2[] can make a pair with arr1[0] i.e. 6.

This process will work because arr1[1] will always be greater than arr1[0] which concludes if arr2[0] and arr2[1] are making a pair with arr1[0], they will obviously make pairs with a number greater than arr1[0] i.e. arr1[1].

Thus before the merge step in the merge sort algorithm, calculate the total number of pairs each time.

Approach

The steps are basically the same as they are in the case of the merge sort algorithm. The change will be just in the mergeSort() function:

In order to count the number of pairs, keep a count variable, cnt, initialized to 0 beforehand inside the mergeSort().

Add the numbers returned by the previous mergeSort() calls. Before the merge step, count the number of pairs using a function, named countPairs(). Remember that the left half starts from low and ends at mid, and the right half starts from mid+1 and ends at high.

The steps of the countPairs() function will be as follows:

Declare a variable, cnt, initialized with 0 & run a loop from low to mid, to select an element at a time from the left half.

Inside that loop, use another loop to check how many elements from the right half can make a pair.

Lastly, add the total number of elements i.e. (right-(mid+1)) (where right = current index), to the cnt and return it. Thus before the merge step in the merge sort algorithm, we will calculate the total number of pairs each time.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to count reverse
    pairs where a[i] > 2 * a[j]*/
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        return team(nums, n);
    }

private:
    /* Merge function to merge two 
    sorted halves and count reverse pairs*/
    void merge(vector<int>& arr, int low, int mid, int high) {
        // temporary array
        vector<int> temp; 
        
        // starting index of left half of arr
        int left = low;  
        
        // starting index of right half of arr
        int right = mid + 1; 

        // Merge and count reverse pairs
        while (left <= mid && right <= high) {
            
            if (arr[left] <= arr[right]) {
                temp.push_back(arr[left]);
                left++;
            } 
            else {
                temp.push_back(arr[right]);
                right++;
                
            }
        }

        // Copy remaining elements from left half
        while (left <= mid) {
            temp.push_back(arr[left]);
            left++;
        }

        // Copy remaining elements from right half
        while (right <= high) {
            temp.push_back(arr[right]);
            right++;
        }

        // Transfer sorted elements from temp to arr
        for (int i = low; i <= high; i++) {
            arr[i] = temp[i - low];
        }
    }
private:
    //Function to count reverse pairs
    int countPairs(vector<int> &arr, int low, int mid, int high) {
        int right = mid + 1;
        int cnt = 0;
        
        for (int i = low; i <= mid; i++) {
            
            /*while right is less than equal to high 
           and arr[i] is greater than 2 * arr[right] 
           then increment right by 1*/
            while (right <= high && arr[i] > 2 * arr[right]) right++;
            
            cnt += (right - (mid + 1));
        }
        //Return the count
        return cnt;
    }
private:
    /* Merge sort function to sort the
    array and count reverse pairs*/
    int mergeSort(vector<int>& arr, int low, int high) {
        int cnt = 0;
        
        if(low >= high){
            return cnt;
        }
        int mid = low + (high - low) / 2;
            
        // Sort left half
        cnt += mergeSort(arr, low, mid); 
            
        // Sort right half
        cnt += mergeSort(arr, mid + 1, high);
        
        cnt += countPairs(arr, low, mid, high);
            
        // Merge and count pairs
        merge(arr, low, mid, high); 
        
        //Return the count of reverse pairs
        return cnt;
    }
private:
    int team(vector <int> & skill, int n){
        return mergeSort(skill, 0, n - 1);
    }
};

int main() {
    vector<int> nums = {6, 4, 1, 2, 7};
    
    //Create an instance of Solution class
    Solution sol;
    
    int cnt = sol.reversePairs(nums);
    
    //Print the count of reverse pairs
    cout << "The number of reverse pairs is: " << cnt << endl;
    return 0;
}
import java.util.*;

class Solution {
    /* Function to count reverse
    pairs where a[i] > 2 * a[j]*/
    public int reversePairs(int[] nums) {
        int n = nums.length;
        return team(nums, n);
    }

    /* Merge function to merge two 
    sorted halves and count reverse pairs*/
    private void merge(int[] arr, int low, int mid, int high) {
        // temporary array
        List<Integer> temp = new ArrayList<>();
        
        // starting index of left half of arr
        int left = low;  
        
        // starting index of right half of arr
        int right = mid + 1; 

        // Merge and count reverse pairs
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp.add(arr[left]);
                left++;
            } else {
                temp.add(arr[right]);
                right++;
            }
        }

        // Copy remaining elements from left half
        while (left <= mid) {
            temp.add(arr[left]);
            left++;
        }

        // Copy remaining elements from right half
        while (right <= high) {
            temp.add(arr[right]);
            right++;
        }

        // Transfer sorted elements from temp to arr
        for (int i = low; i <= high; i++) {
            arr[i] = temp.get(i - low);
        }
    }

    // Function to count reverse pairs
    private int countPairs(int[] arr, int low, int mid, int high) {
        int right = mid + 1;
        int cnt = 0;
        
        for (int i = low; i <= mid; i++) {
            
            /*while right is less than equal to high and arr[i]
            is greater than 2 * arr[right] then increment right by 1*/
            while (right <= high && arr[i] > 2 * arr[right]) right++;
            
            cnt += (right - (mid + 1));
        }
        //Return the count
        return cnt;
    }

    /* Merge sort function to sort the
    array and count reverse pairs*/
    private int mergeSort(int[] arr, int low, int high) {
        int cnt = 0;
        
        if (low >= high) {
            return cnt;
        }
        
        int mid = low + (high - low) / 2;
        
        // Sort left half
        cnt += mergeSort(arr, low, mid);
        
        // Sort right half
        cnt += mergeSort(arr, mid + 1, high);
        
        // Merge and count pairs
        cnt += countPairs(arr, low, mid, high);
        merge(arr, low, mid, high);
        
        //Return the count of reverse pairs
        return cnt;
    }

    private int team(int[] skill, int n) {
        return mergeSort(skill, 0, n - 1);
    }

    public static void main(String[] args) {
        int[] nums = {6, 4, 1, 2, 7};
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        int cnt = sol.reversePairs(nums);
        
        // Print the count of reverse pairs
        System.out.println("The number of reverse pairs is: " + cnt);
    }
}
from typing import List

class Solution:
    """ Function to count reverse
    pairs where a[i] > 2 * a[j]"""
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        return self.team(nums, n)

    """ Merge function to merge two 
    sorted halves and count reverse pairs"""
    def merge(self, arr: List[int], low: int, mid: int, high: int) -> None:
        # temporary array
        temp = []
        
        # starting index of left half of arr
        left = low  
        
        # starting index of right half of arr
        right = mid + 1 

        # Merge and count reverse pairs
        while left <= mid and right <= high:
            if arr[left] <= arr[right]:
                temp.append(arr[left])
                left += 1
            else:
                temp.append(arr[right])
                right += 1

        # Copy remaining elements from left half
        while left <= mid:
            temp.append(arr[left])
            left += 1

        # Copy remaining elements from right half
        while right <= high:
            temp.append(arr[right])
            right += 1

        # Transfer sorted elements from temp to arr
        for i in range(low, high + 1):
            arr[i] = temp[i - low]

    # Function to count reverse pairs
    def countPairs(self, arr: List[int], low: int, mid: int, high: int) -> int:
        right = mid + 1
        cnt = 0
        
        for i in range(low, mid + 1):
            """while right is less than equal to high and arr[i]
            is greater than 2 * arr[right] then increment right by 1"""
            while right <= high and arr[i] > 2 * arr[right]:
                right += 1
            
            cnt += (right - (mid + 1))
        
        # Return the count
        return cnt

    """ Merge sort function to sort the
    array and count reverse pairs"""
    def mergeSort(self, arr: List[int], low: int, high: int) -> int:
        cnt = 0
        
        if low >= high:
            return cnt
        
        mid = (low + high) // 2
        
        # Sort left half
        cnt += self.mergeSort(arr, low, mid)
        
        # Sort right half
        cnt += self.mergeSort(arr, mid + 1, high)
        
        # Merge and count pairs
        cnt += self.countPairs(arr, low, mid, high)
        self.merge(arr, low, mid, high)
        
        # Return the count of reverse pairs
        return cnt

    def team(self, skill: List[int], n: int) -> int:
        return self.mergeSort(skill, 0, n - 1)

if __name__ == "__main__":
    nums = [6, 4, 1, 2, 7]
    
    # Create an instance of the Solution class
    sol = Solution()
    
    cnt = sol.reversePairs(nums)
    
    # Print the count of reverse pairs
    print("The number of reverse pairs is:", cnt)
class Solution {
    /* Function to count reverse
    pairs where a[i] > 2 * a[j]*/
    reversePairs(nums) {
        let n = nums.length;
        return this.team(nums, n);
    }

    /* Merge function to merge two 
    sorted halves and count reverse pairs*/
    merge(arr, low, mid, high) {
        // temporary array
        let temp = [];
        
        // starting index of left half of arr
        let left = low;  
        
        // starting index of right half of arr
        let right = mid + 1; 

        // Merge and count reverse pairs
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp.push(arr[left]);
                left++;
            } else {
                temp.push(arr[right]);
                right++;
            }
        }

        // Copy remaining elements from left half
        while (left <= mid) {
            temp.push(arr[left]);
            left++;
        }

        // Copy remaining elements from right half
        while (right <= high) {
            temp.push(arr[right]);
            right++;
        }

        // Transfer sorted elements from temp to arr
        for (let i = low; i <= high; i++) {
            arr[i] = temp[i - low];
        }
    }

    // Function to count reverse pairs
    countPairs(arr, low, mid, high) {
        let right = mid + 1;
        let cnt = 0;
        
        for (let i = low; i <= mid; i++) {
            /*while right is less than equal to high and arr[i]
            is greater than 2 * arr[right] then increment right by 1*/
            while (right <= high && arr[i] > 2 * arr[right]) right++;
            
            cnt += (right - (mid + 1));
        }
        //Return the count
        return cnt;
    }

    /* Merge sort function to sort the
    array and count reverse pairs*/
    mergeSort(arr, low, high) {
        let cnt = 0;
        
        if (low >= high) {
            return cnt;
        }
        
        let mid = Math.floor((low + high) / 2);
        
        // Sort left half
        cnt += this.mergeSort(arr, low, mid);
        
        // Sort right half
        cnt += this.mergeSort(arr, mid + 1, high);
        
        // Merge and count pairs
        cnt += this.countPairs(arr, low, mid, high);
        this.merge(arr, low, mid, high);
        
        //Return the count of reverse pairs
        return cnt;
    }

    team(skill, n) {
        return this.mergeSort(skill, 0, n - 1);
    }


 static main() {
        const nums = [6, 4, 1, 2, 7];
        
        // Create an instance of Solution class
        let sol = new Solution();
  
        let cnt = sol.reversePairs(nums);
        
        // Print the count of reverse pairs
        console.log("The number of reverse pairs is: " + cnt);
    }
}

// Call the main function to test the Solution class
Solution.main();

Complexity Analysis

Time Complexity: O(2N * logN), where N is size of the given array.

Inside the mergeSort() we call merge() and countPairs() except mergeSort() itself. Now, inside the function countPairs(), though we are running a nested loop, we are actually iterating the left half once and the right half once in total.

That is why, the time complexity is O(N). And the merge() function also takes O(N). The mergeSort() takes O(logN) time complexity. Therefore, the overall time complexity will be O(logN x (N+N)) = O(2NxlogN)

Space Complexity: O(N), as in the merge sort, a temporary array to store elements in sorted order is used.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code