Count of Smaller Numbers After Self

 Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts  array has the property where counts[i] is the number of smaller elements to the right of nums[i].

 

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

 

Constraints:

• 0 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

 class Solution {

public:

    #define vp_itr vector<pair<int,int>> ::iterator 

    void merg_count( vp_itr l,vp_itr r,vector<int> &count)

    {

        if(r-l<=1)

            return;

            

            auto m=l+(r-l)/2;

        merg_count(l,m,count);

        merg_count(m,r,count);

        auto j=m;

        for(auto i=l;i<m;++i)

        {

            while(j<r and (i->first)>(j->first))

                ++j;

            count[i->second]+=j-m;

        }

        std::inplace_merge(l,m,r);

    }

    vector<int> countSmaller(vector<int>& nums) {

        int n=nums.size();

        vector<int> count(n,0);

        vector<pair<int,int>> tmp;

        for(int i=0;i<n;++i)

        {

        tmp.push_back({nums[i],i});

        }

        

        merg_count(tmp.begin(),tmp.end(),count);

        return count;

    }

};