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 <= 105-104 <= nums[i] <= 104
Solution
/**
* @param {number[]} nums
* @return {number[]}
*/
var countSmaller = function(nums) {
var arr = nums.map((num, i) => [num, i]);
var res = Array(nums.length).fill(0);
mergeSort(arr, res);
return res;
};
var mergeSort = function(arr, res) {
if (arr.length === 1) return arr;
var mid = Math.floor(arr.length / 2);
var left = mergeSort(arr.slice(0, mid), res);
var right = mergeSort(arr.slice(mid), res);
return merge(left, right, res);
};
var merge = function(left, right, res) {
var arr = [];
var leftIndex = 0;
var rightIndex = 0;
while (leftIndex < left.length || rightIndex < right.length) {
if (!right[rightIndex] || (left[leftIndex] && left[leftIndex][0] > right[rightIndex][0])) {
arr.push(left[leftIndex]);
res[left[leftIndex][1]] += right.length - rightIndex;
leftIndex += 1;
} else {
arr.push(right[rightIndex]);
rightIndex += 1;
}
}
return arr;
};
Explain:
nope.
Complexity:
- Time complexity : O(n * log(n)).
- Space complexity : O(n).