Count of Smaller Numbers After Self hard
Description
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].
Examples
> Case 1:
nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
Explanation:
To the right of 5 there are 2 smaller (2, 1).
To the right of 2 there is 1 smaller (1).
To the right of 6 there is 1 smaller (1).
To the right of 1 there is 0 smaller.
> Case 2:
nums = [-1]
Output: [0]Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Why brute force is too slow
counts = [sum(1 for j in range(i + 1, len(nums)) if nums[j] < nums[i]) for i in range(len(nums))]O(n²) — TLE for n = 10^5.
The merge-sort-with-extra-accounting approach
Recall from the advanced page: the merge step of merge sort can compute any quantity that depends on cross-pairs between the left and right halves. Here, the quantity is “how many right-half elements are smaller than each left-half element.”
Key insight: during the merge of two sorted halves, when we place a right-half element into the output (before some left-half element), we know that right-half element is smaller than every remaining left-half element. So we add the number of right-half elements moved so far to each left-half element’s count as we place it.
To preserve the original index → count mapping, work on indices instead of values. Sort an index array; the values are looked up by index.
Recurrence: T(n) = 2 T(n / 2) + O(n) → O(n log n).
Why count when placing the LEFT element (not when placing the right element)?
When we move a right-half element into the output, we know it’s smaller than every left-half element STILL waiting in indices[i..mid). But we don’t yet know which left elements those are — by the time we place each left element, we know “how many right elements were placed before me” = right_placed. That value is exactly the count to add for that left element.
Putting the count update on the left-placement step lets us record the contribution in one O(1) addition per left element, rather than adding 1 to many left counts per right placement.
C++ / Java versions
The Python version is the cleanest exposition. C++ / Java versions use the same algorithm but get noisier due to manual index handling — included for completeness:
Alternative — Fenwick tree (BIT)
Coordinate-compress the values, then iterate from right to left maintaining a Fenwick tree over the value space. For each nums[i], query the prefix sum strictly below it, then insert. O(n log n) time, O(n) space. This approach generalizes to other “count something to the right” problems.
Analysis
- Time:
O(n log n). - Space:
O(n)for the index array, merge buffer, and recursion stack.
Same skin
- Count Inversions —
T(n) = 2 T(n / 2) + O(n)via merge sort. - Reverse Pairs — count pairs
(i, j)withi < jandnums[i] > 2 · nums[j]. - Count of Range Sum — merge sort on prefix sums.
- Number of Pairs Satisfying Inequality — similar merge-with-counting framework.
The “merge step with extra accounting” pattern is one of the most powerful D&C techniques. Once it clicks, an entire family of cross-pair counting problems becomes routine.