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:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
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.

// Binary Search
vector<int> countSmaller(vector<int>& nums) { // time: O(nlogn); space: O(n)
    // tmp array records the sorted elements to the right for the current number
    vector<int> tmp, res(nums.size());
    // Scan from the tail of the input array
    for (int i = nums.size() - 1; i >= 0; --i) {
        int left = 0, right = tmp.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tmp[mid] >= nums[i]) right = mid;
            else left = mid + 1;
        }
        res[i] = left;
        tmp.insert(tmp.begin() + left, nums[i]);
    }
    return res;
}

// STL
vector<int> countSmaller(vector<int>& nums) { // time: O(nlogn); space: O(n)
    // tmp array records the sorted elements to the right for the current number
    vector<int> tmp, res(nums.size());
    // Scan from the tail of the input array
    for (int i = nums.size() - 1; i >= 0; --i) {
        int d = distance(tmp.begin(), lower_bound(tmp.begin(), tmp.end(), nums[i]));
        res[i] = d;
        tmp.insert(tmp.begin() + d, nums[i]);
    }
    return res;
}

// Build a binary search tree with an additional variable
struct Node {
    int val, smaller;
    Node *left, *right;
    Node(int v, int s = 0) : val(v), smaller(s), left(nullptr), right(nullptr) {} 
};
int insert(Node*& root, int value) {
    if (!root) {
        root = new Node(value);
        return 0;
    } else if (root->val > value) {
        ++root->smaller;
        return insert(root->left, value);
    } else { // value >= root->val
        return insert(root->right, value) + root->smaller + (value > root->val ? 1 : 0);
    }
}
vector<int> countSmaller(vector<int>& nums) { // time: O(nlogn); space: O(n)
    vector<int> res(nums.size(), 0);
    Node* root = nullptr;
    for (int i = nums.size() - 1; i >= 0; --i) {
        res[i] = insert(root, nums[i]);
    }
    return res;
}