**MergeSort**

**Explanation:** In each round, we divide our array into two parts and sort them. So after "int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); ", the left part and the right part are sorted and now our only job is to count how many pairs of number (leftPart[i], rightPart[j]) satisfies leftPart[i] <= 2*rightPart[j].

For example,

left: 4 6 8 right: 1 2 3

so we use two pointers to travel left and right parts. For each leftPart[i], if j<=e && nums[i]/2.0 > nums[j], we just continue to move j to the end, to increase rightPart[j], until it is valid. Like in our example, left's 4 can match 1 and 2; left's 6 can match 1, 2, 3, and left's 8 can match 1, 2, 3. So in this particular round, there are 8 pairs found, so we increases our total by 8.

```
public class Solution {
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length-1);
}
private int mergeSort(int[] nums, int s, int e){
if(s>=e) return 0;
int mid = s + (e-s)/2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
for(int i = s, j = mid+1; i<=mid; i++){
while(j<=e && nums[i]/2.0 > nums[j]) j++;
cnt += j-(mid+1);
}
Arrays.sort(nums, s, e+1);
return cnt;
}
}
```

**Or:**

Because left part and right part are sorted, you can replace the Arrays.sort() part with a actual merge sort process. The previous version is easy to write, while this one is faster.

```
public class Solution {
int[] helper;
public int reversePairs(int[] nums) {
this.helper = new int[nums.length];
return mergeSort(nums, 0, nums.length-1);
}
private int mergeSort(int[] nums, int s, int e){
if(s>=e) return 0;
int mid = s + (e-s)/2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
for(int i = s, j = mid+1; i<=mid; i++){
while(j<=e && nums[i]/2.0 > nums[j]) j++;
cnt += j-(mid+1);
}
//Arrays.sort(nums, s, e+1);
myMerge(nums, s, mid, e);
return cnt;
}
private void myMerge(int[] nums, int s, int mid, int e){
for(int i = s; i<=e; i++) helper[i] = nums[i];
int p1 = s;//pointer for left part
int p2 = mid+1;//pointer for rigth part
int i = s;//pointer for sorted array
while(p1<=mid || p2<=e){
if(p1>mid || (p2<=e && helper[p1] >= helper[p2])){
nums[i++] = helper[p2++];
}else{
nums[i++] = helper[p1++];
}
}
}
}
```

**BST**

BST solution is no longer acceptable, because it's performance can be very bad, O(n^2) actually, for extreme cases like [1,2,3,4......49999], due to the its unbalance, but I am still providing it below just FYI.

We build the Binary Search Tree from right to left, and at the same time, search the partially built tree with nums[i]/2.0. The code below should be clear enough.

```
public class Solution {
public int reversePairs(int[] nums) {
Node root = null;
int[] cnt = new int[1];
for(int i = nums.length-1; i>=0; i--){
search(cnt, root, nums[i]/2.0);//search and count the partially built tree
root = build(nums[i], root);//add nums[i] to BST
}
return cnt[0];
}
private void search(int[] cnt, Node node, double target){
if(node==null) return;
else if(target == node.val) cnt[0] += node.less;
else if(target < node.val) search(cnt, node.left, target);
else{
cnt[0]+=node.less + node.same;
search(cnt, node.right, target);
}
}
private Node build(int val, Node n){
if(n==null) return new Node(val);
else if(val == n.val) n.same+=1;
else if(val > n.val) n.right = build(val, n.right);
else{
n.less += 1;
n.left = build(val, n.left);
}
return n;
}
class Node{
int val, less = 0, same = 1;//less: number of nodes that less than this node.val
Node left, right;
public Node(int v){
this.val = v;
}
}
}
```

Similar to this https://leetcode.com/problems/count-of-smaller-numbers-after-self/. But the main difference is: here, the number to add and the number to search are different (add nums[i], but search nums[i]/2.0), so not a good idea to combine build and search together.