Count of Smaller Numbers After Self

Problem statement

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.

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

My solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
    if (nums.length === 0 || !nums) {
        return nums;
    }
    
    let inversion = Array.from({
        length: nums.length
    }, () => 0)
    const mapNumsArr = nums.map((val, index) => ({
        val, index
    }))
    
    function mergeSort(arr) {
//         Base case
        if (arr.length === 1) {
            return arr;
        }
        
        const mid = Math.floor(arr.length / 2)
        const leftArr = mergeSort(arr.slice(0, mid));
        const rightArr = mergeSort(arr.slice(mid))
        
        let leftIndex = 0;
        let rightIndex = 0;
        let sortedArr = [];
        let inversionCount = 0;
        while (leftIndex < leftArr.length) {
            if (rightArr[rightIndex] && leftArr[leftIndex].val > rightArr[rightIndex].val) {
//                 Found a greated value
                inversionCount++;
                sortedArr.push(rightArr[rightIndex++])
            } else {
//                 no inversion found
//                 update inversion count
                inversion[leftArr[leftIndex].index] += inversionCount;
                sortedArr.push(leftArr[leftIndex++])
            }
        }
        
        return [...sortedArr, ...rightArr.slice(rightIndex)]
    }
    
    mergeSort(mapNumsArr)
    return inversion;
};