Count of Smaller Numbers After Self

Description

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

Solution(javascript)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
    const sortedElements = [];
    const smallerElements = [];
    for (let i = nums.length - 1; i >= 0; i--) {
        let position = binarySearch(nums[i], sortedElements);
        if (sortedElements[position] >= nums[i] || sortedElements.length === 0) {
            sortedElements.splice(position, 0, nums[i]);
        } else {
            position += 1;
            sortedElements.splice(position, 0, nums[i]);
        }
        smallerElements.unshift(position);
    }
    return smallerElements;
};

const binarySearch = (value, nums) => {
    if (nums.length === 0) return 0;
    let left = 0;
    let right = nums.length - 1;
    let mid = left + Math.floor((right - left) / 2);
    while (left !== right) {
        if (value > nums[mid]) {
            // go right
            left = Math.min(mid + 1, right);
        } else if (value < nums[mid]) {
            // go left
            right = Math.max(mid - 1, left);
        } else {
            // sorta go left
            right = mid;
        }
        mid = left + Math.floor((right - left) / 2);
    }
    return left;
};