> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0493-reverse-pairs.md).

# 0493. Reverse Pairs

<https://leetcode.com/problems/reverse-pairs>

## Description

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
```

**Example 2:**

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

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `-231 <= nums[i] <= 231 - 1`

## ac

```java
class Solution {
    public int reversePairs(int[] nums) {
        // edge cases
        if (nums == null || nums.length <= 1) return 0;

        int n = nums.length;
        int[] bit = new int[n+1];
        int[] reverseSorted = new int[n]; // 3,3,2,1,1
        int[] copy = Arrays.copyOf(nums, n);
        Arrays.sort(copy); 
        for (int i = 0; i < n; i++) reverseSorted[i] = copy[n-1-i];

        int res = 0;
        for (int i = 0; i < n; i++) {
            res += getSum(bit, getBitIndex(reverseSorted, nums[i] * 2l)-1);
            update(bit, getBitIndex(reverseSorted, nums[i]));
        }

        return res;
    }

    private int getBitIndex(int[] nums, long val) {
        // binary search get first index <= val, because we want to find element > val
        int l = 0, r = nums.length-1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] <= val) r =  mid;
            else l = mid;
        }
        int res = nums[l] <= val ? l : nums[r] <= val ? r : r + 1;
        return res + 1;  // it's actually returning the rank
    }
    private int getSum(int[] bit, int i) {
        int res = 0;
        while (i > 0) {
            res += bit[i];
            i -= i & (-i);
        }
        return res;
    }
    private void update(int[] bit, int i) {
        while (i < bit.length) {
            bit[i]++;
            i += i & (-i);
        }
    }
}

/*
1,3,2,3,1
3,3,2,1,1

2,6,4,6,2


2,4,3,5,1
5,4,3,2,1

4,8,6,10,2

*/
```

## ac2: merge

\`\`\`java class Solution { int count = 0; public int reversePairs(int\[] nums) { // edge cases if (nums == null || nums.length <= 1) return 0;

```
    merge(nums, 0, nums.length-1);

    return count;
}
private int[] merge(int[] nums, int start, int end) {
    if (start == end) return new int[]{nums[start]};

    int mid = start + (end - start) / 2;
    int[] left = merge(nums, start, mid);
    int[] right = merge(nums, mid+1, end);

    int[] res = new int[end - start + 1];
    int l = 0, r = 0, i = 0;
    int p = 0;
    while (l < left.length) {
        // extract info
        while (p < right.length && right[p] < left[l] / 2.0) p++;
        count += p;

        // merge process
        while (r < right.length && right[r] < left[l]) res[i++] = right[r++];
        res[i++] = left[l++];
    }
    while (r < right.length) res[i++] = right[r++];

    return res;
}
```

} \`\`