Count of Smaller Numbers After Self
Count of Smaller Numbers After Self: for every array position, count later elements whose values are smaller.
- 1 <= nums.length <= 10⁵
- -10⁴ <= nums[i] <= 10⁴
Intuition
Count of smaller numbers after self asks, for every position, how many later elements are smaller. Scanning the suffix at each index is O(n²). The way past it reuses merge sort, which already compares the two halves against each other while merging — the information is being generated and then thrown away. Here is what the merge step reveals. When both halves are sorted, every element of the right half originally sat after every element of the left half. So when a right-half value is taken before a left-half value during the merge, that right value is a smaller element appearing later — exactly what the problem counts: - Maintain a counter of right-half elements already merged; when a left element is taken, that counter is how many smaller-and-later elements it has seen at this level. Summed across all recursion levels, each left element accumulates its complete answer, because every other element is compared against it at exactly one level. One complication: merge sort moves elements, so an element's array position stops matching its original index. Pair each value with its original index before sorting, and accumulate counts into a result array indexed by that stored value. One detail decides correctness: when values are equal, take from the left half. The problem asks for strictly smaller, so an equal right-hand value must not be counted.
A per-index question about later elements often becomes a crossing-pair count. If relationships can be counted while two sorted halves merge, indexed merge sort gives O(n log n) time.
Approach
Before reading on: price up what the direct approach costs here, then ask what you would need to remember from the left to avoid re-scanning. Aim for O(n log n) time and O(n) space.
Pair values with original indices
Build (value, index) pairs before sorting. Merge sort moves elements, so the stored index is the only way to attribute a count back to the right position in the answer array.
Recurse on both halves
Split and solve each half, which counts all pairs lying entirely within one side. What remains is pairs that cross the midpoint, and those are what the merge step handles.
Count right-half elements as they move
During the merge, increment a counter each time a right-half pair is taken. When a left pair is taken, that counter is its answer contribution — those right elements are both smaller and originally later.
Take from the left on ties
When values are equal, choose the left pair and do not count it. The problem asks for strictly smaller elements, so an equal right-hand value must not contribute.
Accumulate across levels
Add each contribution into result[originalIndex] rather than overwriting. Every pair of elements is compared at exactly one recursion level, so the sums build to the complete answer.
Know the alternative structures
A Binary Indexed Tree, a segment tree, or a balanced BST over value ranks also solves count of smaller numbers after self in O(n log n), processing right to left. Merge sort is usually easier to derive from scratch; the BIT is shorter once you know it.
Cost of the counted merge sort
The recursion has log n levels each doing O(n) merging work, giving O(n log n) time and O(n) space for the pair array and the merge buffer.
Solution & live demo
Common pitfalls
Counting equal values as smaller
if right[j][0] <= left[i][0]:
if right[j][0] < left[i][0]:
The requested relation is strictly smaller, not smaller or equal.
Losing original positions
pairs = sorted(nums)
pairs = [(value, i) for i, value in enumerate(nums)]
Counts must be written back in input order after values move.
Adding all right elements
answer[left[i][1]] += len(right)
answer[left[i][1]] += moved_right
Only right elements already moved ahead are proven smaller than the current left value.
Edge cases
Equality selects the left element, so no false smaller counts are added.
Each left-side item accumulates all smaller items to its right across merge levels.
Comparisons use actual integer values and original indices, so both are handled naturally.