9ms Java BST solution with explanations


  • 4
    M

    When doing insertions in BST, every move (exploring left or right) implies that half of the sub-tree is smaller/greater than the node you're inserting.

    So, this solution exploits this by summing the sizes of left sub-trees one insertion passes.

    This solution deals with equality by counting the occurrences of every node in the BST. In conclusion, counts[i] = sum(sizes of left sub-trees passed + occurrences of the roots of the corresponding sub-trees).

    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
            int len;
            List<Integer> res = new ArrayList<>();
            if (nums == null || (len = nums.length) == 0) {
                return res;
            }
            Integer[] tmp = new Integer[len];
            BST bst = new BST();
            for (int i = len - 1; i >= 0; i--) {
                tmp[i] = bst.insert(nums[i]);
            }
            res.addAll(Arrays.asList(tmp));
            return res;
        }
        
        private static class BST {
            private Node root;
            
            private int insert(int val) {
                int sCnt = 0;
                if (root == null) {
                    root = new Node(val);
                    return sCnt;
                }
                Node cur = root;
                while (true) {
                    if (cur.val < val) {
                        sCnt += cur.lCnt + cur.selfCnt;
                        if (cur.right == null) {
                            cur.right = new Node(val);
                            return sCnt;
                        }
                        else {
                            cur = cur.right;
                        }
                    }
                    else if (cur.val > val) {
                        cur.lCnt++;
                        if (cur.left == null) {
                            cur.left = new Node(val);
                            return sCnt;
                        }
                        else {
                            cur = cur.left;
                        }
                    }
                    // equal
                    else {
                        sCnt += cur.lCnt;
                        cur.selfCnt++;
                        return sCnt;
                    }
                }
            }
        }
        
        private static class Node {
            private int val;
            private Node left;
            private Node right;
            // size for left sub-tree
            private int lCnt;
            // cnt for self occurances
            private int selfCnt;
            
            private Node(int val) {
                this.val = val;
                selfCnt = 1;
            }
        }
    }

Log in to reply
 

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