> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/reverse-pairs.md).

# Reverse Pairs

Given an array `nums`, we call `(i, j)` an **important reverse pair** if `i < j` and `nums[i] > 2*nums[j]`.

You need to return the number of important reverse pairs in the given array.

**Example1:**

```
Input: [1,3,2,3,1]
Output: 2
```

**Example2:**

```
Input: [2,4,3,5,1]
Output: 3
```

**Note:**<br>

1. The length of the given array will not exceed `50,000`.
2. All the numbers in the input array are in the range of 32-bit integer.

```java
class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int start, int end) {
        if (start >= end)
            return 0;
        int mid = start + (end - start) / 2;
        int leftAns = mergeSort(nums, start, mid);
        int rightAns = mergeSort(nums, mid + 1, end);
        return leftAns + rightAns + merge(nums, start, end);
    }

    public int merge(int[] nums, int start, int end) {
        int mid = start + (end - start) / 2;
        int p1 = start, p2 = mid + 1;
        int pointer = mid + 1, index = 0, count = 0;
        int[] temp = new int[end - start + 1];
        while (p1 <= mid) {
            // All the elements behind pointer, are satisfying the equation with "p1"
            while (pointer <= end && 2L * nums[pointer] < (long) nums[p1])
                pointer++;
            count += pointer - (mid + 1);
            while (p2 <= end && nums[p2] < nums[p1])
                temp[index++] = nums[p2++];
            temp[index++] = nums[p1++];
        }
        while (p2 <= end)
            temp[index++] = nums[p2++];
        for (int i = start; i <= end; i++)
            nums[i] = temp[i - start];
        return count;
    }
}
```