Count of Smaller Numbers After Self Hard 0 attempts
LeetCode ↗

Count of Smaller Numbers After Self

Hard Sorting&Searching LeetCode

Given an integer array nums, return an array counts where counts[i] is the number of smaller elements to the right of nums[i].

Example: nums = [5,2,6,1] → Output: [2,1,1,0]

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

Merge Sort with Index Tracking

Count inversions during merge sort by tracking original indices.

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