In this Leetcode Reverse Pairs problem solution 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].

Leetcode Reverse Pairs problem solution


Problem solution in Python.

import bisect 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        count,l=0,[]    
        for i in nums :
            a=bisect.bisect_right  (l,i*2)#finding the index 
            count+=len (l)-a#finding the number of greater than equal to i*2
            idx=bisect.bisect(l,i)#finding the index where the i need to be inserted
            l[idx:idx]=[i]#trick for inserting at idx much faster than insert()
        return count

Problem solution in Java.

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
    private int mergeSort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int count = 0;
        int mid = l + (r - l) / 2;
        count += mergeSort(nums, l, mid);
        count += mergeSort(nums, mid + 1, r);
        count += merge(nums, l, mid, r);
        return count;
    }
    private int merge(int[] nums, int l, int mid, int r) {
        int count = 0, l1 = l, l2 = mid + 1, idx = 0;
        while (l1 <= mid && l2 <= r) {
            if ((long) nums[l1] > (long) 2 * nums[l2]) {
                count += mid - l1 + 1;
                l2++;
            } else l1++;
        }
        l1 = l;
        l2 = mid + 1;
        int[] copy = new int[r - l + 1];
        while (l1 <= mid && l2 <= r) {
            if (nums[l1] > nums[l2]) copy[idx++] = nums[l2++];
            else copy[idx++] = nums[l1++];
        }
        while (l1 <= mid) copy[idx++] = nums[l1++];
        while (l2 <= r) copy[idx++] = nums[l2++];
        System.arraycopy(copy, 0, nums, l, r - l + 1);
        return count;
    }
}


Problem solution in C++.

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        multiset<long long> tb;
        int ret = 0;
        
        int n = nums.size();
        
        for(int i = n - 1; i >= 0; --i) {
            long long cur = nums[i];
            
            auto iter = lower_bound(tb.begin(), tb.end(), cur);
            
            ret +=  distance(tb.begin(), iter);
            tb.insert(2 * cur);
        }
        
        return(ret);
    }
};