9ms short Java BST solution get answer when building BST


  • 176
    M

    Every node will maintain a val sum recording the total of number on it's left bottom side, dup counts the duplication. For example, [3, 2, 2, 6, 1], from back to beginning,we would have:

                    1(0, 1)
                         \
                         6(3, 1)
                         /
                       2(0, 2)
                           \
                            3(0, 1)
    

    When we try to insert a number, the total number of smaller number would be adding dup and sum of the nodes where we turn right.
    for example, if we insert 5, it should be inserted on the way down to the right of 3, the nodes where we turn right is 1(0,1), 2,(0,2), 3(0,1), so the answer should be (0 + 1)+(0 + 2)+ (0 + 1) = 4

    if we insert 7, the right-turning nodes are 1(0,1), 6(3,1), so answer should be (0 + 1) + (3 + 1) = 5

    public class Solution {
        class Node {
            Node left, right;
            int val, sum, dup = 1;
            public Node(int v, int s) {
                val = v;
                sum = s;
            }
        }
        public List<Integer> countSmaller(int[] nums) {
            Integer[] ans = new Integer[nums.length];
            Node root = null;
            for (int i = nums.length - 1; i >= 0; i--) {
                root = insert(nums[i], root, ans, i, 0);
            }
            return Arrays.asList(ans);
        }
        private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
            if (node == null) {
                node = new Node(num, 0);
                ans[i] = preSum;
            } else if (node.val == num) {
                node.dup++;
                ans[i] = preSum + node.sum;
            } else if (node.val > num) {
                node.sum++;
                node.left = insert(num, node.left, ans, i, preSum);
            } else {
                node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
            }
            return node;
        }
    }

  • 2
    J

    Best solution I have ever seen by now for Count of Smaller Numbers After Self! THX.


  • 28
    D

    runtime could be O(n^2) when processing input like n, n-1, ..., 2, 1. I think the test cases are not good enough.


  • 0
    V

    I would agree that worst time complexity is O(n^2). Though it's certainly an interesting approach :).


  • 0

    I just came up with exactly the same solution and was surprised to see the result. In fact, I intended to turn it into a red-black tree, but decided to try first the unbalanced version and got 9 ms. I think test cases really should include one that would prevent such simple solution from being accepted.


  • 19
    E

    Same idea, iterative version, run in 7ms. Listed here only for reference.

    class Node{
        int val, leftSum = 0, count = 0;
        Node left, right;
        public Node(int val){
            this.val = val;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        Integer[] count = new Integer[nums.length];
        if(nums.length == 0){
            return Arrays.asList(count);
        }
        Node root = new Node(nums[nums.length - 1]);
        for(int i = nums.length - 1; i >= 0; i--){
            count[i] = insert(root, nums[i]);
        }
        return Arrays.asList(count);
    }
    private int insert(Node node, int num){
        int sum = 0;
        while(node.val != num){
            if(node.val > num){
                if(node.left == null) node.left = new Node(num);
                node.leftSum++;
                node = node.left;
            }else{
                sum += node.leftSum + node.count;
                if(node.right == null) node.right = new Node(num);
                node = node.right;
            }
        }
        node.count++;
        return sum + node.leftSum;
    }

  • 2
    P

    I only thinking how do you think it .......


  • 1
    H

    Good idea and clear description though in the worst case binary search tree could be a linked list causing O(n^2) in time complexity.


  • 0
    M

    This is so smart!


  • 0
    S

    I wish I could upvote this twice! Brilliant!


  • 8
    L

    There is no need for considering the duplication elements. See the code below which is referred from: http://www.cnblogs.com/grandyang/p/5078490.html

    class TreeNode{
            int smallCount;
            int val;
            TreeNode left;
            TreeNode right;
            public TreeNode(int count, int val){
                this.smallCount = count;
                this.val = val;
            }
        }
        
        public List<Integer> countSmaller(int[] nums) {
            TreeNode root = null;
            Integer[] ret = new Integer[nums.length];
            if(nums == null || nums.length == 0) return Arrays.asList(ret);
            for(int i=nums.length-1; i>=0; i--){
                root = insert(root, nums[i], ret, i, 0);
            }
            return Arrays.asList(ret);
        }
        
        public TreeNode insert(TreeNode root, int val, Integer[] ans, int index, int preSum){
            if(root == null){
                root = new TreeNode(0, val);
                ans[index] = preSum;
            }
            else if(root.val>val){
                root.smallCount++;
                root.left = insert(root.left, val, ans, index, preSum);
            }
            else{
                root.right = insert(root.right, val, ans, index, root.smallCount + preSum + (root.val<val?1:0));//only adding 1 on preSum if root.val is only smaller than val
            }
            return root;
        }
    

  • 1
    Y

    I agree with @liang54 , the dup is unnecessary. My C++ version:

    class Solution {
    public:
        class TreeNode {
            public: 
            int val, smallerCnt;
            TreeNode* left, *right;
            TreeNode(int v, int s) : left(NULL), right(NULL), val(v), smallerCnt(s){}
        };
        
        vector<int> countSmaller(vector<int>& nums) {
            int len = nums.size();
            if(len == 0)    return vector<int>();
            vector<int> ret(len, 0); 
            TreeNode* root = NULL;
            
            for(int i = len-1; i >= 0; --i) 
                root = insert(ret, nums[i], i, 0, root);
    
            return ret;
        }
    
    private:
        TreeNode* insert(vector<int>& ret, int val, int idx, int preSum, TreeNode* node) {
            if(node == NULL) {
                node = new TreeNode(val, 0);
                ret[idx] = preSum;
            }
            else if(node->val > val) {
                node->smallerCnt++;
                node->left = insert(ret, val, idx, preSum, node->left);
            }
            else
                node->right = insert(ret, val, idx, preSum + node->smallerCnt + ((node->val < val)? 1: 0), node->right);
                
            return node;
        }
    };
    

  • 0

    At the very beginning, I was like what is this. After running several test cases I found it is a brilliant solution. By the way, the dup is unnecessary.


  • 0

    Thanks for sharing! I think insert() method could be a little simplified. https://discuss.leetcode.com/topic/55730/my-bst-solution-with-detailed-explanation

        private int insert(BSTNode root, int newval) {
            if (newval < root.val) {
                root.leftsum++;
                if (root.left != null) 
                    return insert(root.left, newval);
                root.left = new BSTNode(newval);
                return 0;
            } else if (root.val < newval) {
                int smaller = root.leftsum + root.dup;
                if (root.right != null)
                    return insert(root.right, newval) + smaller;
                root.right = new BSTNode(newval);
                return smaller;
            } else {
                root.dup++;
                return root.leftsum;
            }
        }
    

  • 0
    H

    @mayanist Can we consider this as insertion sort with O(N*logN), O(N) space and worst O(N^2)?


  • 8

    Awesome solution! Just want to add some comments to make it more readable.
    This BST is a kind of augmented BST, please check this video to learn more about it(Princeton Algorithm: https://www.youtube.com/watch?v=8Samxh_gV-Q).

    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
            if(nums == null || nums.length == 0) return new ArrayList<>();
    
            TreeNode root = null;
            Integer[] res = new Integer[nums.length];
            for(int i = nums.length - 1; i >= 0; i--) {
                root = insert(nums[i], root, res, i, 0);
            }
            return Arrays.asList(res);
        }
    
        private TreeNode insert(int num, TreeNode root, Integer[] res, int index, int preSum) {
            if(root == null) {
                // create new node no matter if it is duplicated
                res[index] = preSum;
                root = new TreeNode(num);
            } else if(num >= root.val) {
                // only change the preSum when going right,
                // 1) preSum is the count before root.parent
                // 2) root.segmentLeftCount is the count between root.parent and root
                // 3) num > root.val ? 1 : 0 is the count of root itself, 
                // if the statement of question is "smaller or equals to", it will be always 1
                root.right = insert(num, root.right, res, index, preSum + root.segmentLeftCount + (num > root.val ? 1 : 0));
            } else {
                // only change segmentLeftCount when going left
                // at this time, root.parent <= num < root, so increase root.segmentLeftCount
                root.segmentLeftCount++;
                root.left = insert(num, root.left, res, index, preSum);
            }
            return root;
        }
    
        class TreeNode {
            public int val, segmentLeftCount = 0;
            TreeNode left = null, right = null;
    
            public TreeNode(int val) {
                this.val = val;
            }
    
            public String toString() {
                return val + "(" + segmentLeftCount + ")";
            }
        }
    }
    

  • 0

    I got this idea, just wonder...how do you figure this out...


  • 0
    W

    a quite simple insert search logic solution.

    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
           List<Integer> result = new LinkedList<>();
           List<Integer> sorted = new ArrayList<>();
           for(int i = nums.length - 1;i >= 0;i--){
               int index = findLess(sorted,nums[i]);
               result.add(0,index);
               sorted.add(index,nums[i]);
           }
           return result;
        }
        public int findLess(List<Integer> sorted,int target){
            if(sorted.isEmpty()) return 0;
            int left = 0,right = sorted.size();
            while(left < right){
                int mid = (left + right)/2;
                if(sorted.get(mid) >= target) right = mid;
                else left = mid + 1;
            }
            return left;
        }
    }
    

  • 0
    C

    @mayanist said in 9ms short Java BST solution get answer when building BST:

    node

    Just wonder, do you need consider balancing the tree? What if a worst case makes your tree looks almost like a very long linked list?


  • 0

    building the tree while processing, the time complex is O(n * log(n)) ?
    n is length of array.
    this method is good when n is small and max value of the array is large.

    while the opposite, n is large and max value is small, segment tree is better


Log in to reply
 

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