Help me out in this

#1



it is giving tle

#2

@KartikKhariwal are u there ?

#3

Yeah checking…

#4

@Kartikkhariwal1 okay bro

#5

Hey @shivammishra20121999
Complexity of distance() is O(n)
So ur complexity becomes O( n^2) hence giving tle for 1 case

#6

@Kartikkhariwal1 then what should i do instead of that?

#7

Here refer to this simple solution

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        std::vector<int> sortedNums;
        std::vector<int> count (nums.size());
        
        for (long i = nums.size() - 1; i >= 0; i--)
        {
            auto itr = std::lower_bound(sortedNums.begin(), sortedNums.end(), nums[i]);
            count[i] = itr - sortedNums.begin();
            sortedNums.insert(itr, nums[i]);
        }
        
        return count;
    }
};
#8

@Kartikkhariwal1
auto itr = std::lower_bound(sortedNums.begin(), sortedNums.end(), nums[i]); time complexirty iska kya haan bhai?

#9

O(logn)…

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.