315 Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].

Brute Force Solution

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 0);
        for ( int i = 0; i <= n-1; i++ ) {
            for ( int j = i-1; j >= 0; j-- ) {
                if ( nums[i] < nums[j] ) res[j] += 1;
            }
        }
        return res;
    }
};

AC Solution!!
Thoughts

• Build a binary search tree from the end of the array.

  e.g. [5, 2, 6, 1]
        1
         \
          6
         / 
        2
         \
          5
  

• When inserting a new node X, the number of nodes smaller than X is just the "smaller numbers after self".
  • How: When comparing with a node Y along the path, if ( X->val > Y->val), then Y and all Y's left sub-tree nodes are smaller than X. (result += 1 + Y->count)

• As stated above, for each node we have to record the number of nodes in its left-subtree, using a variable "count".
  • How: When comparing with a node Y along the path, if ( X->val <= Y->val ), X must have to go into Y's left sub-tree. Y->count += 1.

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