Official 1007 views

Editorial: Count of Smaller Numbers After Self

by admin · Oct. 18, 2026

1 Intuition

Process from the right while keeping the already-seen values sorted.

2 Approach

For each value, its answer is the insertion point in the sorted list of values to its right. A Fenwick tree or merge-sort counting makes every step O(log n).

3 Complexity Analysis

Time O(n log n) with a BIT / merge sort, Space O(n).

4 Solution Code

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        import bisect
        seen, out = [], []
        for x in reversed(nums):
            out.append(bisect.bisect_left(seen, x))
            bisect.insort(seen, x)
        return out[::-1]

5 Code Walkthrough

The reference solution below implements the approach step by step.