Solution to leetcode 315 Count of Smaller Numbers After Self

Problem statement could be found @https://leetcode.com/problems/count-of-smaller-numbers-after-self/

Analysis
This problem can have another form where one is asked to find number of inversions.

Approach
Use merge sort technique ie divide collection (here vector) into smaller parts and count inversions.

Following is the code -
1. Here I'm using a map to count inversions for an integer, hence the limitation of this code it doesn't work with duplicates.
2. Another important point is I'm filling the greatest element in vector first during merge. It helps simplify the code by following logic. So if an element is left half is larger than current element of right half, then following formula gives the count of element in right half with which left element is larger

   valMap[nums[leftBoundary]] = valMap[nums[leftBoundary]] +
                                                                  (rightBoundary - right + 1);

We could have tried filling smaller element first, in that case finding inversions would have taken a for loop.


class Solution {
    map<int, int> valMap;
private:
    void applyMerge(vector<int> &nums, int startIndex, int endIndex){
        if (startIndex >= endIndex){
            return ;
        }
       
        int midIndex = (startIndex+endIndex)/2;
        applyMerge(nums, startIndex, midIndex);
        applyMerge(nums, (midIndex+1),endIndex);
       
        int left = startIndex;
        int right = midIndex+1;
        int leftBoundary = midIndex;
        int rightBoundary = endIndex;
       
        vector<int> temp;
        while ((left<=leftBoundary) && (right<=rightBoundary)){
            if (nums[leftBoundary] > nums[rightBoundary]){
                valMap[nums[leftBoundary]] = valMap[nums[leftBoundary]] +
                                    (rightBoundary - right + 1);
                temp.insert(temp.begin(),nums[leftBoundary] ) ;
                leftBoundary--;
            }else{
                temp.insert(temp.begin(),nums[rightBoundary] ) ;
                rightBoundary--;
            }
        }
        while (right <= rightBoundary){
            temp.insert(temp.begin(),nums[rightBoundary] ) ;
            rightBoundary--;
        }
        while (left<=leftBoundary){
            temp.insert(temp.begin(),nums[leftBoundary] ) ;
            leftBoundary--;
        }
       
        for (int i=0;i<=(endIndex-startIndex);i++){
            nums[i+startIndex] =  temp[i];
        }
     
    }
public:
   
    vector<int> countSmaller(vector<int>& nums) {
        for (int i=0;i<nums.size();i++){
          valMap[nums[i]] = 0;
        }
       
        vector<int> temp(nums);
        vector<int> elemGt;
        applyMerge(nums,0, nums.size()-1);
        for (int i=0;i<temp.size();i++){
            elemGt.push_back(valMap[temp[i]]);
        }
        return elemGt;  
    }
};