vector<int> countSmaller(vector<int>& nums)
{
multiset<int, greater<int>> hmset;
vector<int> result(nums.size(), 0);
int pos = static_cast<int>(nums.size())  1;
for(auto it = nums.rbegin(); it != nums.rend(); ++it)
{
auto iter = hmset.upper_bound(nums[pos]);
result[pos] = distance(iter, hmset.end());
hmset.insert(nums[pos]);
}
return result;
}
Why does my O(n logn) solution timing out?


@nandsatya said in Why does my O(n logn) solution timing out?:
result[pos] = distance(iter, hmset.end());
this is not O(nlogn) but )(n^2) since distance is in linear time.
