Clean Java Solution using Enhanced Binary Search Tree

• This is literally the same problem with 315. Count of Smaller Numbers After Self.
The only difference is to find count of numbers smaller than `half` of the current number after itself.
To efficiently search for count of numbers smaller than a target, we can use a Binary Search Tree. There is a little change of the TreeNode to include count of numbers `smaller or equal` to it. This will make the query even faster because we don't need to traverse all its left sub-tree to get the count.

Overall Algorithm:

1. Scan the numbers from right to left.
2. First search the tree to get `count` of numbers smaller than `nums[i] / 2.0`, sum to the final result.
3. Insert `nums[i]` to the tree.

Insert logic:

1. Recursively try to find a place to insert this number. When root is `null`, its time to create a new node. If meet the `same` number, just increase the `count`.
2. When try to insert the number to left sub-tree, increase `count` of current node.

Query logic:

1. If target value is greater than the current value, meaning current node and all left sub-tree are `smaller` than target, return `count` (remember it stands for count of numbers `smaller or equal` to current number) of current node `plus` any possible smaller number than target in `right` sub-tree.
2. Otherwise, only search `left` sub-tree.
``````public class Solution {
class Node {
int value, count;
Node left, right;
Node (int v) {
value = v; count = 1;
}
}

public int reversePairs(int[] nums) {
int result = 0;
if (nums == null || nums.length <= 1) return result;

int len = nums.length;
Node root = new Node(nums[len - 1]);

for(int i = len - 2; i >= 0; i--) {
result += query(root, nums[i] / 2.0);
insert(root, nums[i]);
}

return result;
}

private Node insert(Node root, int value) {
if (root == null) return new Node(value);

if (root.value == value) {
root.count++;
}
else if (root.value > value) {
root.count++;
root.left = insert(root.left, value);
}
else {
root.right = insert(root.right, value);
}

return root;
}

private int query(Node root, double value) {
if (root == null) return 0;

if (value > root.value) {
return root.count + query(root.right, value);
}
else {
return query(root.left, value);
}
}
}
``````

• @shawngao so great, I still hava a lot to learn, thanks for sharing your idar.

• @shawngao what's the time complexity for this solution? I think at worst case it can be O(n^2).
For example case where all numbers are sorted. 1 2 3 4 5 6 7 8 9 10.
At each iteration you will go to the deepest node on the tree O(n).
Thus, the total complexity could reach O(n^2).
Is there anything that I miss here?

• @qweruiop Yes, you are right. Worst case runtime complexity is O(n^2) because this `home-made` tree is not a balanced tree.

• @shawngao I see. I thought that O(n^2) solution would never pass with such N = 50000. I guess they just check for the average case then. Thank you for the clear solution.

• @shawngao Yes. Not only the not-balancing part is killing the time complicity, but also this part:

``````else if (root.value > value) {
root.count++;
root.left = insert(root.left, value);
}
else {
root.right = insert(root.right, value);
}
``````

basically you need to go through the entire tree (partially built) for querying/searching. So I think the overall time complicity in theory is actually O(n^2)? But, it is, of course, practically much faster than the naive way, just a nested for-loop.

I am thinking, is there a way to make it really O(nlogn)?

• @Chidong I still believe the `Average Runtime Complexity` of this algorithm is O(nlgn) though I can't approve it. Sometime it is good enough :)

Like `Quick Sort`, it's `Worst Case Runtime Complexity` is O(n^2). But in practice, it's much faster than `Bubble sort` etc. Also `HashMap` is another good example, which (put, get operations) have `Average Runtime Complexity` = O(1) but `Worst Case Runtime Complexity` = O(n).

• @shawngao ,"There is a little change of the TreeNode to include count of numbers `smaller or equal` to it."

I think the definition of your TreeNode should be: to include the count of numbers in`its left children and itself`.

• Your code can't pass test now ! I changed it by balancing the tree. but neither do it.

/**

• Created by songbo.han on 2017/2/23.
*/

public class Solution{
public class BNode{
public BNode left, right;
public int data, height, num;
public BNode(int data) {
this.data = data;
}
}

``````private int height(BNode t){
return null == t ? -1 : t.height;
}

private BNode balance(BNode t){
if(height(t.left) - height(t.right) > 1){
if(height(t.left.left) > height(t.left.right))
t = rotateR(t);
else{
t.left = rotateL(t.left);
t = rotateR(t);
}
}
else if(height(t.right) - height(t.left) > 1){
if(height(t.right.right) > height(t.right.left))
t = rotateL(t);
else{
t.right = rotateR(t.right);
t = rotateL(t);
}
}
t.height = Math.max(height(t.left), height(t.right)) + 1;
return t;

}

private BNode rotateR(BNode k2){
//System.out.println("绕" + k2.data + "右旋");
BNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), k2.height) + 1;
return k1;
}

private BNode rotateL(BNode k2){
//System.out.println("绕" + k2.data + "左旋");
BNode k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.right), k2.height) + 1;
return k1;
}

public BNode insert(BNode t, int target){
if(null == t)
return new BNode(target);
else{
if(t.data > target)
t.left = insert(t.left, target);
else
t.right = insert(t.right, target);

return balance(t);
}
}

public int find(BNode t, double target){
if(null == t)
return 0;
if(t.data >= target)
return find(t.left, target);
else
return find(t.left, target) + find(t.right, target) + 1;
}

public int reversePairs(int[] nums) {
int result = 0;
if (nums == null || nums.length <= 1) return result;

int len = nums.length;
BNode root = new BNode(nums[len - 1]);
for (int i = len - 2; i >= 0; i--) {
result += find(root, nums[i] / 2.0);
root = insert(root, nums[i]);
}

return result;

}
``````

}

• this solution cannot pass tests now, tests include sequences like 1,2,3,4...(sorted)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.