Problem
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 <= 10^5-10^4 <= nums[i] <= 10^4
Solution
/**
* @param {number[]} nums
* @return {number[]}
*/
var countSmaller = function(nums) {
const smallerArr = Array(nums.length).fill(0);
function mergeSort(nums) {
if (nums.length <= 1) return nums;
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let l = 0, r = 0;
while (l < left.length || r < right.length) {
if (r >= right.length || (l < left.length && left[l][1] <= right[r][1])) {
result.push(left[l]);
smallerArr[left[l][0]] += r;
l += 1;
} else {
result.push(right[r]);
r += 1;
}
}
return result;
}
const temp = [];
nums.map((e,i) => temp.push([i, e]));
mergeSort(temp);
return smallerArr;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).