C++ 36ms BST solution.


  • 9

    The insert function will return the total number of nums smaller than x, and also put x in the right place.

    struct node{
        int val,copy,leftCnt;
        node *left,*right;
        node(int x){val=x;copy=1;leftCnt=0;left=NULL;right=NULL;}
    };
    
    int insert(node* root,int x){
        if (root->val==x){
            root->copy++;
            return root->leftCnt;
        }else if (root->val>x){
            root->leftCnt++;
            if (root->left==NULL) {
                root->left = new node(x);
                return 0;
            }else  return insert(root->left,x);
        }else{
            if (root->right==NULL){
                root->right = new node(x);
                return root->leftCnt+root->copy;
            }else return root->leftCnt+root->copy+insert(root->right,x);
        }
    }
    
    class Solution {
    public:
    vector<int> countSmaller(vector<int>& nums) {
        int sz=nums.size();
        vector<int> res(sz,0);
        if (sz<=1) return res;
        node *root = new node(nums[sz-1]);
        for (int i=sz-2;i>=0;i--){
            res[i] = insert(root,nums[i]);
        }
        return res;
    }
    };

  • 0

    Thank you for your BST solution, I have learned a lot from this solution,


  • 1
    W

    I wonder is the time complexity of this algorithm still O(n^2) since it may not be a balance binary tree?

    For example,

    [100, 99, 98, ...., 3, 2, 1]

    Thanks!


  • 0
    C

    Thank you for providing solution, i tried a lot ,but i didn't this approach was good


  • 0

    @weihsin.chen.906 You're right. If you want guaranteed O(n log n), you need a self-balancing tree such as an AVL tree or red-black tree.


  • 0
    B

    @weihsin.chen.906 It doesn't matter. using a self balance tree doesn't change the code much.


  • 0
    Y

    This is the AVL Tree version, it will cause TLE. :/ (15/16 cases passed.)
    I guess it only optimizes for sorted arrays, like [100, 99, 98,98, ...]. But for normal cases, it takes a lot more time to balance the tree.

    // AVL TREE ////////////////////////////
    struct Node {
        int val;
        int height;
        int occur;
        int leftCnt;
        Node *left;
        Node *right;
        
        // constructor, destructor
        Node(int x) : val(x), height(0), occur(1), leftCnt(0), left(0), right(0){ }
        ~Node() { delete left; left = 0; delete right; right = 0; }
        
        // insert
        int insert(int x) {
            if (x == val) {
                ++occur;
                return leftCnt;
            } else if (x < val) {
                ++leftCnt;
                if (!left) {
                    left = new Node(x);
                    return 0;
                } else return left->insert(x);
            } else {
                if (!right) {
                    right = new Node(x);
                    return leftCnt + occur;
                } else return leftCnt + occur + right->insert(x);
            }
            return -1;
        }
    };
        
    class BST {
    private :
    	Node *root;
    	Node *balance(Node *n);
    	int height(Node *n) { if (!n) return 0; return max(height(n->left), height(n->right)) + 1; }
    	int diff(Node *n) { return height(n->left) - height(n->right); }
    	Node *rr_rotation(Node *n); // Right - Right Rotation
    	Node *ll_rotation(Node *n); // Left - Left Rotation
    	Node *rl_rotation(Node *n); // Right - Left Rotation
    	Node *lr_rotation(Node *n); // Left - Right Rotation
    public :
    	BST() : root(0) { }
    	~BST() { if (root) delete root; root = 0; }
    	int insert(int val) { 
    	    if (!root) { root = new Node(val); return 0; }
    	    int res = root->insert(val); 
    	    root = balance(root); // balance tree after insertion
    	    return res;
    	}
    };
    
    // Implement rotation and balance functions
    Node *BST::balance(Node *n) {
    	int fct = diff(n);
    	if (fct > 1) {
    		if (diff(n->left) > 0) n = rr_rotation(n);
    		else n = lr_rotation (n);
    	}
    	if (fct < -1) {
    		if (diff(n->right) > 0) n = rl_rotation(n);
    		else n = ll_rotation (n);
    	}
    	return n;
    }
    Node *BST::rr_rotation(Node *n) {
    	Node *temp = n->left;
    	n->left = temp->right;
    	// change leftCnt
    	if (temp->right) 
    	    n->leftCnt = temp->right->leftCnt + temp->right->occur;
    	else n->leftCnt = 0;
    	temp->right = n;
    	return temp;
    }
    Node *BST::ll_rotation(Node *n) {
    	Node *temp = n->right;
    	n->right = temp->left;
    	temp->left = n;
    	// change leftCnt
    	temp->leftCnt = n->leftCnt + n->occur;
    	return temp;
    }
    Node *BST::rl_rotation(Node *n) {
    	Node *temp = n->right;
    	n->right = rr_rotation(temp);
    	return ll_rotation(n);
    }
    Node *BST::lr_rotation(Node *n) {
    	Node *temp = ll_rotation(n->left);
    	n->left = temp;
    	n->left->leftCnt = temp->leftCnt + temp->occur; // change leftCnt
    	return rr_rotation(n);
    }
    
    // SOLUTION ///////////////////////////////////////////
    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            int n = nums.size();
            vector<int> res(n, 0);
            BST tree; // AVL Tree
            for (int i = n - 1; i >= 0; --i) {
                res[i] = tree.insert(nums[i]);
            }
            return res;
        }
    };
    

Log in to reply
 

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