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;
};