14-line 44ms c++, building BST


  • 4
    W
    class Solution {
    public:
        struct Node {
            int val, smaller;
            Node *left, *right;
            Node(int value, int small) { 
                left=right=NULL, val=value, smaller=small; 
            }
        };
        
        int insert(Node *&root, int value) {
            if (root==NULL)
                return (root=new Node(value, 0)), 0;
                
            if (value < root->val) 
                return root->smaller++, insert(root->left, value);
            else
                return insert(root->right, value) + root->smaller + (value>root->val ? 1 : 0);
        }
        
        vector<int> countSmaller(vector<int>& nums) {
            Node *root = NULL;
            deque<int> ans;
            for (int i=nums.size()-1; i>=0; i--)
                ans.push_front(insert(root, nums[i]));
                
            return vector<int> (ans.begin(), ans.end());
        }
    };

  • 0

    Nice neat solution, thanks for sharing!


  • 0
    B

    Great solution with neat code


  • 0
    S

    @wangjiashi can you explain your code, the insert part. Thank you!


Log in to reply
 

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