Count of Smaller Numbers After Self Solutions in C++

// Source : https://leetcode.com/problems/count-of-smaller-numbers-after-self/
// Author : Calinescu Valentin, Hao Chen
// Date   : 2015-12-08




class BinarySearchTreeNode
{
    public:
        int val;     
        int less;      // count of members less than val
        int count;     // count of members equal val
        BinarySearchTreeNode *left, *right;
        BinarySearchTreeNode(int value) : val(value), less(0),count(1),left(NULL), right(NULL) {}
};

class BinarySearchTree
{
    private:
        BinarySearchTreeNode* root;
    public:
        BinarySearchTree(const int value):root(new BinarySearchTreeNode(value)){ }
        ~BinarySearchTree() {
            freeTree(root);
        }
        void insert(const int value, int &numLessThan) {
            insert(root, value, numLessThan);
        }
    private:
        void freeTree(BinarySearchTreeNode* root){
            if (root == NULL) return;
            if (root->left) freeTree(root->left);
            if (root->right) freeTree(root->right);
            delete root;
        }

        void insert(BinarySearchTreeNode* root, const int value, int &numLessThan) {

            if(value < root->val) {  // left
                root->less++;
                if(root->left == NULL) {
                    root->left = new BinarySearchTreeNode(value);
                }else{
                    this->insert(root->left, value, numLessThan);
                }
            } else if(value > root->val) { // right
                numLessThan += root->less + root->count;
                if(!root->right) {
                    root->right = new BinarySearchTreeNode(value);
                }else{
                    this->insert(root->right, value, numLessThan);
                }
            } else {
                numLessThan += root->less;
                root->count++;
                return;
            }
        }
};

class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> counts(nums.size());
            if(nums.size() == 0) return counts;

            BinarySearchTree tree(nums[nums.size()-1]);

            for(int i = nums.size() - 2; i >= 0; i--) {
                int numLessThan = 0;
                tree.insert( nums[i], numLessThan);
                counts[i] = numLessThan;
            }
            return counts; 
        }
};

/// Source : https://leetcode.com/problems/count-of-smaller-numbers-after-self/
/// Author : liuyubobobo
/// Time   : 2018-12-03

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// Using BST
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class BST{

private:
    class TreeNode{
    public:
        int val, sz;
        TreeNode *left, *right;
        TreeNode(int val): val(val), sz(1), left(NULL), right(NULL){}
    };
    TreeNode* root;

public:
    BST(): root(NULL){}

    void add(int x){
        root = add(root, x);
    }

    int smaller_than(int x){
        return smaller_than(root, x);
    }

private:
    TreeNode* add(TreeNode* node, int x){
        if(!node)
            return new TreeNode(x);

        if(x <= node->val)
            node->left = add(node->left, x);
        else
            node->right = add(node->right, x);
        node->sz ++;
        return node;
    }

    int smaller_than(TreeNode* node, int x){

        if(!node)
            return 0;

        if(x <= node->val)
            return smaller_than(node->left, x);
        return (node->left ? node->left->sz : 0) + 1 + smaller_than(node->right, x);
    }
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {

        vector<int> res;
        if(nums.size() == 0)
            return res;

        res.push_back(0);
        if(nums.size() == 1)
            return res;

        BST bst;
        bst.add(nums.back());
        for(int i = nums.size() - 2; i >= 0; i --){
            bst.add(nums[i]);
            res.push_back(bst.smaller_than(nums[i]));
        }
        reverse(res.begin(), res.end());
        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {5, 2, 6, 1};
    print_vec(Solution().countSmaller(nums1));
    // 2 1 1 0

    vector<int> nums2 = {2, 0, 1};
    print_vec(Solution().countSmaller(nums2));
    // 2 0 0

    return 0;
}

/// Source : https://leetcode.com/problems/count-of-smaller-numbers-after-self/
/// Author : liuyubobobo
/// Time   : 2018-12-03

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// Using Merge Sort
/// Sort (value, index) pair to track every element's index
///
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {

        int n = nums.size();

        vector<pair<int, int>> elements;
        for(int i = 0; i < n; i ++)
            elements.push_back(make_pair(nums[i], i));

        vector<int> res(n, 0);
        vector<pair<int, int>> aux(n);
        merge_sort(elements, 0, n - 1, aux, res);
        return res;
    }

private:
    void merge_sort(vector<pair<int, int>>& arr, int l, int r,
                    vector<pair<int, int>>& aux, vector<int>& res){

        if(l >= r)
            return;

        int mid = (l + r) / 2;
        merge_sort(arr, l, mid, aux, res);
        merge_sort(arr, mid + 1, r, aux, res);
        if(arr[mid] > arr[mid + 1])
             merge(arr, l, mid, r, aux, res);
    }

    void merge(vector<pair<int, int>>& arr, int l, int mid, int r,
               vector<pair<int, int>>& aux, vector<int>& res){

        for(int i = l; i <= r; i ++)
            aux[i] = arr[i];
        int i = l, j = mid + 1;
        for(int k = l; k <= r; k ++)
            if(i > mid)
                arr[k] = aux[j], j ++;
            else if(j > r)
                arr[k] = aux[i], res[aux[i].second] += j - mid - 1, i ++;
            else if(aux[i] <= aux[j])
                arr[k] = aux[i], res[aux[i].second] += j - mid - 1, i ++;
            else
                arr[k] = aux[j], j ++;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {5, 2, 6, 1};
    print_vec(Solution().countSmaller(nums1));
    // 2 1 1 0

    vector<int> nums2 = {2, 0, 1};
    print_vec(Solution().countSmaller(nums2));
    // 2 0 0

    return 0;
}

/// Source : https://leetcode.com/problems/count-of-smaller-numbers-after-self/
/// Author : liuyubobobo
/// Time   : 2018-12-03

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// Using Merge Sort
/// Using indexes arr to track every element's index
///
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {

        int n = nums.size();

        vector<int> indexes(n); // indexes[i] : 在排序过程中，nums第i个元素
                                //              对应初始nums中indexes[i]的位置
                                // indexes[2] = 5 表示现在nums中第2个元素，在初始nums中索引为5的位置
        for(int i = 0; i < n; i ++)
            indexes[i] = i;

        vector<int> res(n, 0);
        vector<int> aux(n);
        merge_sort(nums, 0, n - 1, indexes, aux, res);
        return res;
    }

private:
    void merge_sort(vector<int>& arr, int l, int r,
                    vector<int>& indexes, vector<int>& aux, vector<int>& res){

        if(l >= r)
            return;

        int mid = (l + r) / 2;
        merge_sort(arr, l, mid, indexes, aux, res);
        merge_sort(arr, mid + 1, r, indexes, aux, res);
        if(arr[mid] > arr[mid + 1])
            merge(arr, l, mid, r, indexes, aux, res);
    }

    void merge(vector<int>& arr, int l, int mid, int r,
               vector<int>& indexes, vector<int>& aux, vector<int>& res){

        for(int i = l; i <= r; i ++)
            aux[i] = arr[i];

        vector<int> new_indexes(r - l + 1);
        int i = l, j = mid + 1;
        for(int k = l; k <= r; k ++)
            if(i > mid)
                arr[k] = aux[j], new_indexes[k - l] = indexes[j], j ++;
            else if(j > r)
                arr[k] = aux[i], new_indexes[k - l] = indexes[i], res[indexes[i]] += j - mid - 1, i ++;
            else if(aux[i] <= aux[j])
                arr[k] = aux[i], new_indexes[k - l] = indexes[i], res[indexes[i]] += j - mid - 1, i ++;
            else
                arr[k] = aux[j], new_indexes[k - l] = indexes[j], j ++;

        for(int k = l; k <= r; k ++)
            indexes[k] = new_indexes[k - l];
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {5, 2, 6, 1};
    print_vec(Solution().countSmaller(nums1));
    // 2 1 1 0

    vector<int> nums2 = {2, 0, 1};
    print_vec(Solution().countSmaller(nums2));
    // 2 0 0

    return 0;
}