DEV Community

Discussion on: Daily Challenge #256 - How Many Are Smaller Than I?

View post
Collapse
 
vidit1999 profile image
Vidit Sarkar •

Here is a C++ solution,

vector<int> smaller(vector<int> arr){
    map<int, int> m;
    vector<int> ans(arr.size(), 0);

    for(int i = arr.size()-1; i >= 0; i--){
        auto it = m.insert({arr[i], m[arr[i]]++});

        for(auto itr = m.begin(); itr != it.first; itr++) ans[i] += (*itr).second;
    }

    return ans;
}

Test cases,

smaller([5, 4, 3, 2, 1]) => [4, 3, 2, 1, 0]
smaller([1, 2, 0]) => [1, 1, 0]
smaller([1, 2, 3]) => [0, 0, 0]
smaller([1, 1, -1, 0, 0]) => [3, 3, 0, 0, 0]
smaller([5, 4, 7, 9, 2, 4, 4, 5, 6]) => [4, 1, 5, 5, 0, 0, 0, 0, 0]