Count of Smaller Numbers After Self

This is Counting Inversions with one change: instead of one total, you want a count per element. It is a well-known hard problem, and it is a good test of whether you understand why the counting merge works, because you have to decide exactly which element each count belongs to.

There is also a tempting shortcut with a sorted list and binary search. It is short and often fast enough, and its worst case is quietly O(n²). Knowing that — and saying it — is part of the answer.

The problem

Given an array of integers, return an array counts where counts[i] is the number of elements to the right of index i that are strictly smaller than nums[i].

• [7, 3, 9, 2, 3] → [3, 1, 2, 0, 0]. Right of the 7 are 3, 9, 2, 3: three are smaller. Right of the first 3 are 9, 2, 3: only the 2 is smaller, since equal does not count.
• [4, 3, 2, 1] → [3, 2, 1, 0].

Constraints: 1 ≤ n ≤ 10⁵, values between −10⁴ and 10⁴.

Clarifying questions

• Strictly smaller? Yes; equal values do not count.
• Duplicates? Yes, as in the example.
• Output in the original order? Yes, counts[i] for the input's index i.
• Negative values? Yes, which matters for any counting-array approach.

Approach 1: the simple way

For each index, scan everything to its right.

def count_smaller_brute(nums: list[int]) -> list[int]:    n = len(nums)    return [sum(1 for j in range(i + 1, n) if nums[j] < nums[i]) for i in range(n)]

O(n²) time. Measured, 10⁴ elements took about 2 seconds, so 10⁵ would take a few minutes. Every element re-scans the same suffix.

Approach 2: a sorted list and binary search

Walk from right to left, keeping every value seen so far in a sorted list. For each new value, binary search tells you how many seen values are smaller — exactly the answer — and then insert it.

1from bisect import bisect_left, insort234def count_smaller_bisect(nums: list[int]) -> list[int]:5    """Walk right to left, keeping the values seen so far in a sorted list."""6    seen: list[int] = []7    result = [0] * len(nums)8    for i in range(len(nums) - 1, -1, -1):9        result[i] = bisect_left(seen, nums[i])     # how many seen values are smaller10        insort(seen, nums[i])                      # O(n) shift in the worst case11    return result

bisect_left returns the position before any equal values, which is the count of strictly smaller ones. The search is O(log n), but inserting into a Python list is O(n), because everything after the insertion point shifts. So the worst case is O(n²) — for example an increasing array, where every insert goes to the front. Measured on 10⁵ increasing values it took about 2.7 seconds against 0.15 seconds for the merge version below. It is a fine first answer if you say its real complexity.

The key insight

Split the array into left and right halves. For an element in the left half, the smaller elements to its right are of two kinds: those in the left half after it (recursion handles them) and all smaller elements in the right half, since the whole right half lies to its right.

Now merge the two sorted halves. When a left element x is placed, the right elements already placed are exactly the right-half elements smaller than x. If j right elements have been placed, x earns j. Unlike Counting Inversions, the count is credited when a left element is placed, and it goes to that element.

One problem: sorting moves elements, so how do you know which original index to credit? Sort indices, not values. Merge lists of indices, comparing nums[index]. The index travels with the value, and counts[index] += j credits the right element.

Ties need care. For a left x and an equal right y, y is not smaller, so x must be placed before y — take from the right only when it is strictly smaller.

Approach 3: optimised — merge sort on indices

1def count_smaller(nums: list[int]) -> list[int]:2    """Merge sort on indices; credit each left item with the smaller right items."""3    counts = [0] * len(nums)45    def sort_idx(idx: list[int]) -> list[int]:6        if len(idx) <= 1:7            return idx8        mid = len(idx) // 29        left, right = sort_idx(idx[:mid]), sort_idx(idx[mid:])10        merged, i, j = [], 0, 011        while i < len(left) and j < len(right):12            if nums[right[j]] < nums[left[i]]:13                merged.append(right[j])      # a smaller value from the right side14                j += 115            else:16                counts[left[i]] += j         # right[0..j-1] were all smaller17                merged.append(left[i])18                i += 119        for k in range(i, len(left)):20            counts[left[k]] += j             # every right item was smaller21            merged.append(left[k])22        merged.extend(right[j:])23        return merged2425    sort_idx(list(range(len(nums))))26    return counts

Dry run on [7, 3, 9, 2, 3] (written value@index). The array splits into indices [0, 1] and [2, 3, 4], and the right part splits again into [2] and [3, 4].

The small merges first. Merging [0] with [1]: 3@1 is smaller than 7@0, so it goes first; then 7@0 is placed with j = 1, so counts[0] += 1. Merging [3] with [4]: 2@3 is placed first with j = 0; nothing is credited. Merging [2] with [3, 4]: 2@3 and 3@4 are both smaller than 9@2 and go first; 9@2 is placed with j = 2, so counts[2] += 2.

The top merge, of left [1, 0] (values 3, 7) with right [3, 4, 2] (values 2, 3, 9):

The left side is used up, and 9@2 is copied. Final counts: index 0 has 1 + 2 = 3, index 1 has 1, index 2 has 2, and indices 3 and 4 have 0 — [3, 1, 2, 0, 0]. Note the tie: 3@1 was placed before the equal 3@4, so the equal value was not counted.

Complexity: O(n log n) time, guaranteed — merge sort with O(1) extra work per step. O(n) space for the index lists and counts.

Edge cases

• One element: [0].
• All equal, [2, 2, 2]: ties always take the left element first, so every count is 0.
• Strictly decreasing, [4, 3, 2, 1]: [3, 2, 1, 0] — every element to the right is smaller.
• Negative values: only comparisons are used, so nothing changes. (A counting-array or Fenwick approach would need an offset or compression.)

Follow-ups

• Count larger elements to the left instead? Reverse the array and negate the values, then run the same function (and reverse the result).
• Count elements to the right in a value range [lo, hi]? Use a Fenwick tree over compressed values: query ≤ hi minus < lo.
• Only the total? That is Counting Inversions — sum this array.