Count of Smaller Numbers After Self Hard 0 attempts
LeetCode ↗

Count of Smaller Numbers After Self

Hard Sorting&Searching LeetCode

You're given an integer array nums. Build an array counts where counts[i] tells you how many elements located after index i are smaller than nums[i].

Input Format
Implement countSmaller(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
nums = [5,2,6,1]
Output
[2,1,1,0]

Example 2

Input
nums = [2,2,1]
Output
[1,1,0]
Constraints
  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
Test Cases (2)
Case 1
Args: [[5,2,6,1]] Expected: [2,1,1,0]
Case 2
Args: [[2,2,1]] Expected: [1,1,0]
Topics
Sorting&Searching

Merge Sort with Index Tracking

Count inversions during merge sort by tracking original indices.

javascript
function countSmaller(nums) {
  const n = nums.length, counts = Array(n).fill(0);
  const indices = nums.map((_, i) => i);
  function mergeSort(lo, hi) {
    if (hi - lo <= 1) return;
    const mid = (lo + hi) >> 1;
    mergeSort(lo, mid); mergeSort(mid, hi);
    const temp = [];
    let i = lo, j = mid;
    while (i < mid && j < hi) {
      if (nums[indices[i]] > nums[indices[j]]) { counts[indices[i]] += hi - j; temp.push(indices[i++]); }
      else temp.push(indices[j++]);
    }
    while (i < mid) temp.push(indices[i++]);
    while (j < hi) temp.push(indices[j++]);
    for (let k = lo; k < hi; k++) indices[k] = temp[k - lo];
  }
  mergeSort(0, n);
  return counts;
}

Time: O(n log n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript