# Leetcode Reverse Pairs problem solution

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].

## 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);
}
};
```