C++ easy 15 lines solution


  • 7
    A
    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            if (nums.empty()) return {};
            vector<int> hash;
            vector<int> counts(nums.size());
            for (int i = nums.size() - 1; i >= 0; --i)
            {
                auto end = lower_bound(hash.begin(), hash.end(), nums[i]);
                counts[i] = end - hash.begin();
                hash.insert(end, nums[i]);
            }
            return counts;
        }
    };

  • 0
    M

    Shouldn't this solution have complexity of O(n^2) since insertion at the hash could cost up to O(n)?


Log in to reply
 

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