Share my BST solution O(n * log(n) * h) where h is the height of the tree


  • 0
    C

    I used a binary search tree and inserted node from right to left. After each insertion the algorithm keeps track of the count of node to the left. The total count for each element in the array is the depth of the node plus the sum of the count of all the nodes to the left.

    Time complexity:

    1. Insert into the BST: logn.

    2. Get count from BST: h (h is the height of the BST)

    It does both of these steps n times so the total time would be O(n * log(n) * h)

    class Node {
        constructor(val){
            this.val = val;
            this.count = 0;
            this.left = null;
            this.right = null;
            this.parent = null;
        }
    
        insert(val,count){
            var cnode = this;
            var lastNode = this;
            while( cnode ){
                lastNode = cnode;
                if( val > cnode.val ){
                    cnode = cnode.right;
                } else {
                    cnode = cnode.left;
                }
            }
    
            var newNode = new Node(val);
            newNode.parent = lastNode;
            if(val > lastNode.val){
                lastNode.right = newNode;
            } else {
                lastNode.left = newNode;
            }
    
    
            cnode = newNode;
            while(cnode){
                if(cnode.parent && cnode.parent.left === cnode){
                    cnode.parent.count++;
                }
                cnode = cnode.parent;
            }
            return newNode;
        }
    
        countLessThan() {
            var count = 0;
            var cnode = this;
            while(cnode){
                if(cnode.parent && cnode.parent.right === cnode){
                    count += 1 + cnode.parent.count;
                }
                cnode = cnode.parent;
            }
            return count;
        }
    
    }
    
    /**
     * @param {number[]} nums
     * @return {number[]}
     */
    var countSmaller = function(nums) {
        var result = [];
        var len = nums.length;
        result[len-1]=0;
        var root = new Node(nums[len-1],0);
        for(var i = len - 2; i >= 0; i--){
            var newNode = root.insert(nums[i]);
            result[i] = newNode.countLessThan();
        }
        return result;
    
    };

Log in to reply
 

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