Count of Smaller Numbers After Self
Given an integer array nums, return an array counts where countsi is the number of elements to the right of numsi that are smaller than numsi. A brute-force pairwise check is O(n²). Instead, pair each value with its original index and merge sort by value — whenever the merge takes a value from the left run, every right-run value already taken is both smaller and originally to the right, so add that running count directly to the left value's total.
Constraints
- 0 ≤ nums.length ≤ 105
- -104 ≤ numsi ≤ 104
Example
nums = [5, 2, 6, 1][2, 1, 1, 0]Explanation To the right of 5 there are 2 smaller values (2 and 1); to the right of 2 there is 1 (1); to the right of 6 there is 1 (1); to the right of 1 there are none.
Merge sort by value, tracking each original index
Pair each value with its original index; split [5, 2, 6, 1] into [5, 2] and [6, 1].
What happens in this step
indexed = [{val:5,i:0}, {val:2,i:1}, {val:6,i:2}, {val:1,i:3}]
counts = [0, 0, 0, 0]
mergeSort splits at mid=2:
left = [{val:5,i:0}, {val:2,i:1}]
right = [{val:6,i:2}, {val:1,i:3}]
Both halves still have 2 entries, so each recurses one level further before merging.Steps to visualize
- Pair every value with its original index so the count can be tracked as elements move during merging.
- Recursively split and merge like ordinary merge sort, sorting by value.
- Whenever a value is taken from the left run, add however many right-run values have already been taken — those are guaranteed both smaller and originally to the right.
- Add these counts up across every merge call at every level of the recursion.
- The final count for each original index is the number of smaller values that appeared after it.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Pair each value with its original index; split [5, 2, 6, 1] into [5, 2] and [6, 1].
What happens in this step
indexed = [{val:5,i:0}, {val:2,i:1}, {val:6,i:2}, {val:1,i:3}]
counts = [0, 0, 0, 0]
mergeSort splits at mid=2:
left = [{val:5,i:0}, {val:2,i:1}]
right = [{val:6,i:2}, {val:1,i:3}]
Both halves still have 2 entries, so each recurses one level further before merging.Solution
function countSmaller(nums) {
const n = nums.length;
const counts = new Array(n).fill(0);
const indexed = nums.map((val, i) => ({ val, i }));
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
const merged = [];
let i = 0;
let j = 0;
let rightTaken = 0;
while (i < left.length && j < right.length) {
if (left[i].val <= right[j].val) {
counts[left[i].i] += rightTaken;
merged.push(left[i]);
i++;
} else {
rightTaken++;
merged.push(right[j]);
j++;
}
}
while (i < left.length) {
counts[left[i].i] += rightTaken;
merged.push(left[i]);
i++;
}
while (j < right.length) {
merged.push(right[j]);
j++;
}
return merged;
}
mergeSort(indexed);
return counts;
}- Time
- O(n log n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [5, 2, 6, 1] | [2, 1, 1, 0] | example from the docstring |
nums = [] | [] | empty array |
nums = [1] | [0] | smallest valid input, a single element |
nums = [1, 2, 3, 4] | [0, 0, 0, 0] | already ascending, nothing smaller ever follows |
nums = [4, 3, 2, 1] | [3, 2, 1, 0] | fully descending, every later value is smaller |
nums = [2, 2, 2] | [0, 0, 0] | equal values never count as smaller |
nums = [0, -1] | [1, 0] | negative values compared against non-negative ones |
nums = [1, 3, 2] | [0, 1, 0] | only one later element is smaller than an earlier one |