C++ 36ms BST solution.

• 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;
}
};

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

• 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!

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

• @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.

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

• 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;
}
};

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