Last updated on October 25th, 2024 at 10:37 pm

Here, We see Reverse Pairs LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Reverse Pairs LeetCode Solution

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

1. Reverse Pairs LeetCode Solution C++

class Solution {
public:
    int reversePairs(vector<int>& nums) {
         int n = nums.size();
        long long reversePairsCount = 0;
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                if(nums[i] > 2*(long long)nums[j]){
                    reversePairsCount++;
                }
            }
        }
        return reversePairsCount;       
    }
};

2. Reverse Pairs LeetCode Solution Java

class Solution {
    int count;
    public int reversePairs(int[] nums) {
        count = 0;
        merger(nums,0,nums.length-1);

        return count;
    }
    private ArrayList<Integer> merge(ArrayList<Integer> left,ArrayList<Integer> right){
        ArrayList<Integer> ans = new ArrayList<>();
        int i = 0;
        int j = 0;
        while(i < left.size() && j < right.size()){
            if (left.get(i) >right.get(j)){
                ans.add(right.get(j));
                j++;
            }
            else {
                ans.add(left.get(i));
                i++;
            }
        }
        if ( i < left.size()){
            while (i <left.size())
             ans.add(left.get(i++));
        }
        if(j < right.size()){
            while (j < right.size())
             ans.add(right.get(j++));
        }
        return ans;
    }
    private void helper(ArrayList<Integer> left,ArrayList<Integer> right){
        int i = 0;
        int j = 0;
        while (i < left.size() && j < right.size()){
            if(left.get(i) > 2*(long)right.get(j)){
                count += left.size() - i;
                j++;
            }
            else
            i++;
        }
        
    }
    private ArrayList<Integer> merger(int[] nums,int start,int end){
        if(start == end){
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(nums[start]);
            return temp;
        }
        int mid = (start + end)/2;
        ArrayList<Integer> left = merger(nums,start,mid);
        ArrayList<Integer> right = merger(nums,mid+1,end);
        helper(left,right);
        
        return merge(left,right);

    }
}

3. Reverse Pairs Solution JavaScript

var reversePairs = function(nums) {
    let count = 0;
    
    const mergeSort = (nums, low, high) => {
        if (low < high) {
            const mid = Math.floor((low + high) / 2);
            mergeSort(nums, low, mid);
            mergeSort(nums, mid + 1, high);
            count += merge(nums, low, mid, high);
        }
    };
    
    const merge = (nums, low, mid, high) => {
        let count = 0;
        const temp = [];
        let i = low;
        let j = mid + 1;
        while (i <= mid && j <= high) {
            if (nums[i] <= 2 * nums[j]) {
                i++;
            } else {
                count += mid - i + 1;
                j++;
            }
        }
        i = low;
        j = mid + 1;
        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                temp.push(nums[i]);
                i++;
            } else {
                temp.push(nums[j]);
                j++;
            }
        }
        while (i <= mid) {
            temp.push(nums[i]);
            i++;
        }
        while (j <= high) {
            temp.push(nums[j]);
            j++;
        }
        for (let k = 0; k < temp.length; k++) {
            nums[low + k] = temp[k];
        }
        return count;
    };
    mergeSort(nums, 0, nums.length - 1);
    return count;
};

4. Reverse Pairs Solution Python

class Solution(object):
    def reversePairs(self, nums):
        def merge_sort(start, end):
            if start >= end:
                return 0
            mid = (start + end) // 2
            count = merge_sort(start, mid) + merge_sort(mid + 1, end)
            i = start
            j = mid + 1
            while i <= mid and j <= end:
                if nums[i] > 2 * nums[j]:
                    count += mid - i + 1
                    j += 1
                else:
                    i += 1
            nums[start:end + 1] = sorted(nums[start:end + 1])
            return count
        return merge_sort(0, len(nums) - 1)