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

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;
}

} ``