Array     Binary Indexed Tree     Binary Search     C++     Divide and Conquer     Hard     Merge Sort     Ordered Set     Segment Tree    

Problem Statement:

Given an integer array nums, return an integer array counts 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.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Solution:

Here is a typical pseudocode for mergeSort:

 
void mergeSort(vector<int>&A, int lo, int hi)
{
    int mid = lo+(hi-lo)/2;
    mergeSort(A,lo,mid);
    mergeSort(A,mid+1,hi);
    merge(); // merge logic in same or separate function
}

Now in the merge logic we typically have this kind of logic:

 
int i=0, j=0, k=0, n1=L.size(), n2=R.size();
vector<int> A(n1+n2);
while(i<n1 && j<n2) if(L[i]<=R[j]) A[k++]=L[i++]; else A[k++]=R[j++];
while(i<n1) A[k++]=L[i++];
while(j<n2) A[k++]=R[j++];

This is for ascending order. For descending order, we just invert the inequality sign.

Now, for our question, if we store the indices with the values in pair<int,int> format, then we can modifty the merge logic to incorporate counting “Lower To the Right” logic.

This can be done in multiple ways as shown below:

Solution 1: Sort in ascending order

 
#define pii pair<int,int>
class Solution {
    vector<int>res;
public:
    void mergeSort(vector<pii>&A, int lo, int hi)
    {
        if (lo==hi) return;
        int mid = lo + (hi-lo)/2;
        mergeSort(A, lo, mid);
        mergeSort(A,mid+1,hi);
        vector<pii> L(A.begin()+lo,A.begin()+mid+1);
        vector<pii> R(A.begin()+mid+1,A.begin()+hi+1);
        int n1=L.size(), n2=R.size(), i=0, j=0, k=lo, ctr=0;
        while(i<n1 && j<n2) 
        {
            if(L[i].first<=R[j].first) 
            {
                res[L[i].second] += ctr;
                A[k++]=L[i++];
            } 
            else
            {
                ctr++;
                A[k++]=R[j++];
            }
        }
        while(i<n1) 
        {
            res[L[i].second] += ctr;
            A[k++]=L[i++];
        }
        while(j<n2) A[k++]=R[j++];
    }
    vector<int> countSmaller(vector<int>& nums) 
    {
        int n = nums.size();
        res.resize(n,0);
        vector<pii> pairs;
        for(int i=0; i<n; i++) pairs.push_back({nums[i],i});
        mergeSort(pairs,0,n-1);
        for(auto k: pairs) cout<<k.first<<',';
        return res;        
    }
};

Solution 2: Sort in descending order

 
#define pii pair<int,int>
class Solution {
    vector<int>res;
public:
    void mergeSort(vector<pii>&A, int lo, int hi)
    {
        if (lo==hi) return;
        int mid = lo + (hi-lo)/2;
        mergeSort(A, lo, mid);
        mergeSort(A,mid+1,hi);
        vector<pii> L(A.begin()+lo,A.begin()+mid+1);
        vector<pii> R(A.begin()+mid+1,A.begin()+hi+1);
        int n1=L.size(), n2=R.size(), i=0, j=0, k=lo;
        while(i<n1 && j<n2) if(L[i].first>R[j].first) 
        {
            res[L[i].second]+=(n2-j); 
            A[k++]=L[i++];
        }  else A[k++]=R[j++];
        while(i<n1) A[k++]=L[i++];
        while(j<n2) A[k++]=R[j++];
    }
    vector<int> countSmaller(vector<int>& nums) 
    {
        int n = nums.size();
        res.resize(n,0);
        vector<pii> pairs;
        for(int i=0; i<n; i++) pairs.push_back({nums[i],i});
        mergeSort(pairs,0,n-1);
        // for(auto k: pairs) cout<<k.first<<',';
        return res;        
    }
};