Count of Smaller Numbers After Self Solution

Problem

Given an array of integers, return a new array where each position holds the count of elements that are strictly smaller and appear to the right of the original element.

Input: nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
Explanation: To the right of 5 are two smaller values (2 and 1); to the right of 6 is one (1); 1 has nothing after it.

Counter-example: [3, 3, 3] → [0, 0, 0] — equal elements do not count as smaller.

Intuition

For each element we need to count how many values to its right are strictly smaller. A brute-force scan works but re-examines the same pairs repeatedly. The key insight is that merge sort already compares every left-half element against every right-half element while merging — we can piggyback the count on those comparisons at no extra asymptotic cost, turning O(n²) into O(n log n).

Approach 1 — Brute Force

For each element, scan every element to its right and count those that are strictly smaller.

Initialize a counts array of zeros with the same length as nums.
For each index i from 0 to n-2, iterate j from i+1 to n-1.
If nums[j] < nums[i], increment counts[i].
Return counts.

1def countSmaller(nums: list[int]) -> list[int]:
2    n = len(nums)
3    counts = [0] * n
4    for i in range(n - 1):
5        for j in range(i + 1, n):
6            if nums[j] < nums[i]:
7                counts[i] += 1
8    return counts

Time: O(n²) — every pair (i, j) with i < j is compared exactly once.
Space: O(n) — only the output array; no extra work space.

Approach 2 — Modified Merge Sort

Augment merge sort to count inversions: when a right-half element is placed before left-half elements during merging, it is smaller than all those not-yet-merged left elements — so each earns a +1.

Pair each value with its original index so positions survive reordering during sort.
Recursively sort the left and right halves.
During merge, maintain right_picks — how many right-half elements have been placed so far.
When a right element is smaller than the current left element, append it and increment right_picks.
When a left element is taken, add right_picks to that element's count (those right elements are all smaller and originally appeared to its right).
After the main loop, flush any remaining left elements — each still earns the final right_picks.

1def countSmaller(nums: list[int]) -> list[int]:
2    n = len(nums)
3    counts = [0] * n
4    # pair each element with its original index to write results to the right slot after sorting
5    pairs = list(enumerate(nums))
6
7    def merge_sort(arr: list) -> list:
8        if len(arr) <= 1:
9            return arr
10        mid = len(arr) // 2
11        left = merge_sort(arr[:mid])
12        right = merge_sort(arr[mid:])
13        return merge(left, right)
14
15    def merge(left: list, right: list) -> list:
16        result = []
17        left_ptr = right_ptr = 0
18        right_picks = 0  # right elements placed before any remaining left elements
19
20        while left_ptr < len(left) and right_ptr < len(right):
21            orig_left_idx, left_val = left[left_ptr]
22            _, right_val = right[right_ptr]
23            if right_val < left_val:
24                result.append(right[right_ptr])
25                right_ptr += 1
26                right_picks += 1  # one more right element is smaller than all remaining left
27            else:
28                counts[orig_left_idx] += right_picks  # right_picks right elements are all smaller
29                result.append(left[left_ptr])
30                left_ptr += 1
31
32        while left_ptr < len(left):  # flush remaining left elements
33            orig_left_idx, _ = left[left_ptr]
34            counts[orig_left_idx] += right_picks
35            result.append(left[left_ptr])
36            left_ptr += 1
37
38        result.extend(right[right_ptr:])
39        return result
40
41    merge_sort(pairs)
42    return counts

Time: O(n log n) — standard merge sort with O(1) extra work per element comparison.
Space: O(n) — the temporary merge buffer and recursion stack are both proportional to n.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(n)	Only for very small inputs or as a correctness baseline
Modified Merge Sort	O(n log n)	O(n)	General case — handles duplicates and large arrays efficiently

Common Mistakes

Forgetting to track original indices — once elements are rearranged by merge sort, their positions change; pairing each value with its original index before sorting is what lets you write into the correct counts slot instead of a wrong one.
Not flushing remaining left elements after the merge loop exits — when the right subarray empties first, the while loop ends, but remaining left elements still need right_picks added; omitting that flush loop silently undercounts for those positions.
Using <= instead of < in the merge comparison — the problem asks for strictly smaller; using <= would treat equal elements as smaller than each other and inflate counts wherever duplicates appear to the right.
Sorting nums in place instead of working on index-value pairs — modifying the original array destroys the positional information needed to write results into the correct counts index.
Applying right_picks to right-half elements instead of left-half ones — it's the left-half elements whose counts grow when right-half elements are placed before them, not the other way around; swapping the update target produces results for the wrong half.

Count of Smaller Numbers After Self — Solution