# 493. Reverse Pairs

Given an array`nums`, we call`(i, j)`animportant reverse pairif`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:

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.

Thoughts:

1. Implementation of BST (Binary Search Tree):

1. Node { val, cnt (sub-problem result), left, right}

2. for each element in the nums: perform search and insert: search element >= 2nums[i] + 1 from the root, and insert val into the root.

3. implementation of search:

1. if root is none -> return
2. if val < root.val -> meaning hitting the upper bound -> return root.cnt + search (root.left, val)
3. if val == root.val -> return root.cnt
4. if val > root.val -> meaning current root.val in not the upper bound -> search (root.right, val)
4. T: O(nlogn) - O(n^2)

2. Implementation of BIT (Binary Indexed Tree):

1. Sort the original array into a copy

2. For each element in the original array sequentially:

1. Using binary search to find corresponding index in the sorted array from the element in the original array

2. Search in the BIT and then Insert the entry into BIT

3. Implementation of Merge Sort:

1. For partition recurrence relation, setting`i = 0, j = n - 1, m = (n-1)/2`, we have:`T(0, n - 1) = T(0, m) + T(m + 1, n - 1) + C`

2. where the subproblem`C`now reads "find the number of important reverse pairs with the first element of the pair coming from the left subarray`nums[0, m]`while the second element of the pair coming from the right subarray`nums[m + 1, n - 1]`".

3. Again for this subproblem, the first of the two aforementioned conditions is met automatically. As for the second condition, we have as usual this plain linear scan algorithm, applied for each element in the left (or right) subarray. This, to no surprise, leads to the`O(n^2)`naive solution.

4. Fortunately the observation holds true here that the order of elements in the left or right subarray does not matter, which prompts sorting of elements in both subarrays. With both subarrays sorted, the number of important reverse pairs can be found in linear time by employing the so-called two-pointer technique: one pointing to elements in the left subarray while the other to those in the right subarray and both pointers will go only in one direction due to the ordering of the elements.

5. The last question is which algorithm is best here to sort the subarrays. Since we need to partition the array into halves anyway, it is most natural to adapt it into a`Merge-sort`. Another point in favor of`Merge-sort`is that the searching process above can be embedded seamlessly into its merging stage.

6. So here is the`Merge-sort`-based solution, where the function`"reversePairsSub"`will return the total number of important reverse pairs within subarray`nums[l, r]`. The two-pointer searching process is represented by the nested`while`loop involving variable`p`, while the rest is the standard merging algorithm.

4. Reference

Code : BST (LTE) since O(n^2) for data like [1,2,3....]

``````class Solution(object):
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
root = None
for num in nums:
ans += self.search(root, (num << 1) + 1)
root = self.insert(root, num)

return ans

def search(self, root, val):
if root is None:
return 0
elif val < root.val:
return root.cnt + self.search(root.left, val)
elif val == root.val:
return root.cnt
else:
return self.search(root.right, val)

def insert(self, root, val):
if root is None:
root = BSTNode(val)
elif val < root.val:
root.left = self.insert(root.left,val)
elif val == root.val:
root.cnt+= 1
else:
root.cnt+= 1
root.right = self.insert(root.right, val)
return root
class BSTNode(object):

def __init__ (self, val):
self.val = val
self.cnt = 1
self.left = self.right = None
``````

Code : BIT T: O(nlogn)

``````class Solution(object):
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def index (arr, val):
l, r, m = 0, len(arr) - 1, 0
while(l <= r):
m = l + ((r - l)>> 1)
if(arr[m] >= val):
r = m - 1
else:
l = m + 1
return l + 1
def search(bit, i):
s = 0
while i < len(bit): # this problem asks "greater than", opposite to the conventional BIT
s += bit [i]
i += i & -i
return s
def insert(bit, i): # this problem asks "greater than", opposite to the conventional BIT
while i > 0 :
bit[i] += 1
i -= i& -i
ans = 0
bit = [0] * (len(nums) + 1)
sortedNums = sorted(nums)
for num in nums:
ans += search(bit, index(sortedNums, 2L * num + 1))
insert( bit,  index(sortedNums, num))
return ans
``````

Code: Merge-Sort T: O(nlogn)

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

private int reversePairsHelper(int [] nums, int l, int r){
if(l >= r ) return 0;

int m = l + ((r - l) >> 1);
int ans = reversePairsHelper(nums, l, m) + reversePairsHelper(nums, m + 1, r);

int left = l, right = m + 1, i = 0, pair = m + 1;
int [] merge = new int[r - l + 1];

while(left <= m){
// search
while(pair <= r && nums[left] > 2L * nums[pair]) pair++;
ans += pair - (m + 1);

// merge (insert)

while(right <= r && nums[left] >= nums[right]) merge[i++] = nums[right++];
merge[i++] = nums[left++];
}

// add the leftover from right to r;
while(right <= r) merge[i++] = nums[right++];

System.arraycopy(merge, 0, nums, l, merge.length);

return ans;
}

}
``````