How Many Numbers Are Smaller Than the Current Number (LeetCode 1365)

For each nums[i], count how many other values in the array are strictly smaller. Values are between 0 and 100.

Three answers, in the order you should give them

Brute force. Two nested loops, O(n squared). Fine to mention, not to stop at.

Sort and look up. Sort a copy. The first index where a value appears equals how many values are smaller than it.

def smallerNumbersThanCurrent(nums):
    first = {}
    for i, v in enumerate(sorted(nums)):
        first.setdefault(v, i)
    return [first[v] for v in nums]

Prefix counts. The value range is tiny, so count each value and take a running sum. The number smaller than v is the total count of values 0 through v-1.

def smallerNumbersThanCurrent(nums):
    cnt = [0] * 102
    for v in nums:
        cnt[v + 1] += 1
    for i in range(1, 102):
        cnt[i] += cnt[i - 1]
    return [cnt[v] for v in nums]

That is O(n + k) time with k = 101.

Interview notes

• Ask about the value range early; it is what unlocks the linear solution.
• Explain the off-by-one shift (cnt[v + 1]) before you write it.
• Duplicates are handled for free by both the first-index and prefix approaches.

If you want an AI assistant for technical interviews to practise these trade-off explanations with, that is what we build at Linkjob AI (disclosure: I work there).