Hard

Count of Smaller Numbers After Self

LAB

For each nums[i], return the count of smaller numbers to its right.

EXAMPLES

Example 1

Input
{
  "nums": [
    5,
    2,
    6,
    1
  ]
}

Output
[
  2,
  1,
  1,
  0
]

FUNCTION SHAPE

nums: intArray→intArray

SOLUTION NOTE

Key insight: segment tree indices = value ranks, values = frequencies. Query [0, rank-1] gives count of smaller elements. Process right-to-left so tree only contains elements to the right.

Reveal reference solution +

pythonREFERENCE

def countSmaller(self, nums: List[int]) -> List[int]:
    # Coordinate compression
    rank = {v: i for i, v in enumerate(sorted(set(nums)))}
    n = len(nums)

    # Segment tree for frequency counting
    tree = SegTree([0] * len(rank), 0, len(rank) - 1)
    res = [0] * n

    # Process right to left
    for i in range(n - 1, -1, -1):
        r = rank[nums[i]]
        # Count elements with rank < r (smaller values)
        res[i] = tree.query(0, r - 1) if r > 0 else 0
        # Add current element to tree (increment frequency)
        tree.update(r, tree.query(r, r) + 1)

    return res

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗