My C++ BST based solution, 36 ms O(NlogN) average complexity, O(N) space


  • 0
    D

    The basic idea is to process num[i] one by one starting from the right side (i.e. i=n-1..0). For each num[i], insert it into a BST built with num[k] (k>i). Each BST node has a field count to save the number of nodes of the subtree rooted at such node. When doing insertion, it uses the count field to calculate res. I tried to use multset to implement such insert sorting, but multiset in C++ doesn't provide O(logN) distance operation, even it is implemented with RB tree.

    class BSTNode{
        public:
        int count, val;
        BSTNode *left, *right;
        BSTNode(int value, int cnt) {
            val = value; 
            count = cnt;  // count is the # of nodes of the subtree rooted at this node.
            left=right=nullptr;
        }
    };
    
    class Solution {
    private: 
        int insertNum(BSTNode *root, int num, int cnt){ //cnt is the number of nodes that have less than num values from layers higher than root
            ++(root->count); // increase root node counter
            if(root->val == num)  // if root has value of num, then the number of nodes less than num is cnt + number of nodes of its left subtree 
                return cnt + (root->left!=nullptr? root->left->count:0);  
            else if(root->val > num) 
            { // goes into the left subtree, do recursiion
                if(!root->left) root->left = new BSTNode(num,0); 
                return insertNum(root->left, num, cnt);
            }
            else 
            { // goes into the right-subtree, update cnt as cnt + the number of nodes of its left subtree + the number of nodes with value of root->val
                if(!root->right) root->right = new BSTNode(num,0); 
                return insertNum(root->right, num, cnt+root->count-root->right->count-1);
            }
        }
        void deleteTree(BSTNode *root)
        {//recursive destroy the tree
            if(root)
            {
                deleteTree(root->left);
                deleteTree(root->right);
                delete root;
            }
        }
        
    public:
        vector<int> countSmaller(vector<int>& nums) {
            int i, nSize = nums.size();
            vector<int> res(nSize,0);
            if(nSize>1)
            {
                BSTNode *root = new BSTNode(nums[nSize-1], 1);
                for(i = nSize-2; i>=0; --i) res[i] = insertNum(root, nums[i], 0);
                deleteTree(root);
            }
            return res;    
        }
    };
    

    The version without dynamic BST Node new/delete

    class BSTNode{
        public:
        int count, val;
        BSTNode *left, *right;
        BSTNode(int value=0, int cnt=0) {
            val = value;
            count = cnt; 
            left=right=nullptr;
        }
    };
    
    class Solution {
    private: 
        int insertNum(BSTNode *root, BSTNode *node, int cnt){
            ++(root->count);
            if(root->val == node->val) 
                return cnt + (root->left!=nullptr? root->left->count:0);
            else if(root->val > node->val) 
            {
                if(!root->left) root->left = node; 
                return insertNum(root->left, node, cnt);
            }
            else 
            {
                if(!root->right) root->right = node; 
                return insertNum(root->right, node, cnt+root->count-root->right->count-1);
            }
        }
    
    public:
        vector<int> countSmaller(vector<int>& nums) {
            int i, nSize = nums.size();
            if(nSize<=1) return vector<int>(nSize, 0);
            vector<int> res(nSize,0);
            BSTNode nodes[nSize];
            for(nodes[nSize-1].val = nums[nSize-1], nodes[nSize-1].count =1, i = nSize-2; i>=0; --i) 
            {
                nodes[i].val = nums[i];
                res[i] = insertNum(&nodes[nSize-1], &nodes[i], 0);
            }
            return res;    
        }
    };

Log in to reply
 

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