##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/493.html

# 493. Reverse Pairs

Hard

## Description

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.

Example 1:

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

Output: 2

Example 2:

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

Output: 3

Note:

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.

## Solution

Use the idea of merge sort. In merge sort, the original array is split into two parts, each of which is sorted, and then merged. Suppose the two parts have already been sorted. Before merging the two parts, if there exists an index i in the left part and an index j in the right part such that nums[i] > 2 * nums[j], then all indices from i to the end of the left part have numbers greater than 2 * nums[j], so increase the count accordingly.

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

public int mergeSortAndCount(int[] nums, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int midIndex = (endIndex - startIndex) / 2 + startIndex;
int count = mergeSortAndCount(nums, startIndex, midIndex) + mergeSortAndCount(nums, midIndex + 1, endIndex);
int index1 = startIndex, index2 = midIndex + 1;
while (index1 <= midIndex && index2 <= endIndex) {
if ((long) nums[index1] > 2 * (long) nums[index2]) {
count += midIndex - index1 + 1;
index2++;
} else
index1++;
}
merge(nums, startIndex, midIndex, endIndex);
return count;
} else
return 0;
}

public void merge(int[] nums, int startIndex, int midIndex, int endIndex) {
int length = endIndex - startIndex + 1;
int[] newArray = new int[length];
int index1 = startIndex, index2 = midIndex + 1;
int index = 0;
while (index1 <= midIndex && index2 <= endIndex) {
if (nums[index1] <= nums[index2])
newArray[index++] = nums[index1++];
else
newArray[index++] = nums[index2++];
}
while (index1 <= midIndex)
newArray[index++] = nums[index1++];
while (index2 <= endIndex)
newArray[index++] = nums[index2++];
for (int i = 0; i < length; i++)
nums[startIndex + i] = newArray[i];
}
}

• // OJ: https://leetcode.com/problems/reverse-pairs/
// Time: O(NlogN)
// Space: O(N)
class Solution {
vector<int> tmp;
int ans = 0;
void solve(vector<int> &A, int begin, int end) {
if (begin + 1 >= end) return;
int mid = (begin + end) / 2, i = begin, j = mid, k = begin, t = mid;
solve(A, begin, mid);
solve(A, mid, end);
for (; i < mid; ++i) {
while (j < end && A[j] < A[i]) {
tmp[k++] = A[j++];
}
while (t < end && (long)A[t] * 2 < A[i]) ++t;
ans += t - mid;
tmp[k++] = A[i];
}
for (; j < end; ++j) tmp[k++] = A[j];
for (int i = begin; i < end; ++i) A[i] = tmp[i];
}
public:
int reversePairs(vector<int>& A) {
tmp.assign(A.size(), 0);
solve(A, 0, A.size());
return ans;
}
};

• class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)

@staticmethod
def lowbit(x):
return x & -x

def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)

def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s

class Solution:
def reversePairs(self, nums: List[int]) -> int:
s = set()
for num in nums:
alls = sorted(s)
m = {v: i for i, v in enumerate(alls, 1)}
ans = 0
tree = BinaryIndexedTree(len(m))
for num in nums[::-1]:
ans += tree.query(m[num] - 1)
tree.update(m[num * 2], 1)
return ans

############

import bisect

class Solution(object):
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
ans = 0
bst = []
for num in nums:
right = 2 * num
idx = bisect.bisect_right(bst, right)
ans += len(bst) - idx
bisect.insort(bst, num)
return ans


• type BinaryIndexedTree struct {
n int
c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += this.lowbit(x)
}
}

func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= this.lowbit(x)
}
return s
}

func reversePairs(nums []int) int {
s := make(map[int]bool)
for _, num := range nums {
s[num] = true
s[num*2] = true
}
var alls []int
for num := range s {
alls = append(alls, num)
}
sort.Ints(alls)
m := make(map[int]int)
for i, num := range alls {
m[num] = i + 1
}
tree := newBinaryIndexedTree(len(m))
ans := 0
for i := len(nums) - 1; i >= 0; i-- {
ans += tree.query(m[nums[i]] - 1)
tree.update(m[nums[i]*2], 1)
}
return ans
}