Clean Java Solution using Enhanced Binary Search Tree


  • 11

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

  • 1
    J

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


  • 0
    Q

    @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?


  • 0

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


  • 0
    Q

    @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.


  • 0

    @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)?


  • 0

    @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).


  • 0

    @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 inits left children and itself.


  • 1
    Y

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

    }


Log in to reply
 

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