How Many Numbers Are Smaller Than the Current Number Solution

Problem

Given an array of integers, figure out for each element how many values in the same array are strictly smaller than it. Return a new array where each position holds that count.

Example:

Input: nums = [8, 1, 2, 2, 3]
Output: [4, 0, 1, 1, 3]
Explanation: 8 has four numbers smaller than it (1, 2, 2, 3), 1 has none, each 2 has one (just the 1), and 3 has three (1, 2, 2).

A counter-example: for nums = [5, 5, 5], all answers are 0 — equal values do not count.

Intuition

For each element, you need the count of values that fall below it. The brute-force is to check every other element; the key insight that unlocks linear time is that each value is between 0 and 100, so you can count every value's frequency in one pass, then turn those frequencies into prefix sums where prefix[v] directly answers "how many elements are less than v."

Approach 1 — Brute Force

For each element, scan the entire array and count how many values are strictly smaller than it.

Create an output array of the same length.
For each index i, initialize a counter to zero.
For each index j, if nums[j] < nums[i] increment the counter.
Store the counter at result[i].
Return the output array.

1class Solution:
2    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
3        result = []
4        for i in range(len(nums)):
5            count = 0
6            for j in range(len(nums)):
7                if nums[j] < nums[i]:  # strictly less than — equal values must not count
8                    count += 1
9            result.append(count)
10        return result

Time: O(n²) — every pair of indices is compared once.
Space: O(n) — only the output array; no auxiliary structure.

Approach 2 — Counting Sort with Prefix Sums

Because values are bounded between 0 and 100, build a frequency array in one pass, then convert it to a prefix sum so that freq[v] becomes the number of elements strictly less than v. Each answer is then a direct lookup.

Allocate freq[0..101] initialized to zero (size 102 covers values 0–100 with a one-cell buffer).
Increment freq[num] for every num in nums.
Accumulate: for each v from 1 to 101, add freq[v - 1] into freq[v]. After this step, freq[v] equals the count of all elements with value ≤ v.
For each original value num, the answer is freq[num - 1] (elements ≤ num − 1 = elements < num). Handle num == 0 separately: nothing is smaller than 0.
Return the result array.

1class Solution:
2    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
3        freq = [0] * 102  # indices 0–100; extra cell avoids bounds checks
4        for num in nums:
5            freq[num] += 1
6
7        # after this loop, freq[v] = count of all elements with value <= v
8        for v in range(1, 102):
9            freq[v] += freq[v - 1]
10
11        # freq[num - 1] = count of elements <= num - 1 = count of elements < num
12        return [0 if num == 0 else freq[num - 1] for num in nums]

Time: O(n + k) where k = 101 — one pass to count, one pass over the fixed range, one pass to build output; effectively O(n).
Space: O(k) = O(1) — the frequency array is fixed size regardless of input length.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(n)	Tiny inputs or when you need to explain the naive solution first
Counting Sort	O(n)	O(1)	Default choice whenever values are bounded by a small constant

Common Mistakes

Using <= instead of < in the brute force — the problem asks for strictly smaller; <= overcounts by including equal elements.
Reading freq[num] instead of freq[num - 1] in the prefix sum — after accumulation, freq[num] includes elements equal to num; you want only those strictly below it.
Not handling num == 0 — freq[-1] is out of bounds in most languages; 0 always has an answer of 0 because no non-negative integer is less than 0.
Forgetting to run the prefix sum step — it's easy to count frequencies and then accidentally return freq[num] directly, which only gives the count of that exact value, not smaller values.
Using the index in a sorted copy as the answer without deduplicating — two identical values land at different sorted positions but must produce the same answer; the prefix-sum approach handles this automatically since both map to freq[value - 1].

How Many Numbers Are Smaller Than the Current Number — Solution