How Many Numbers Are Smaller Than the Current Number
Easy Counting array
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
For every element, report how many other elements in the array are strictly smaller than it. Values are between 0 and 100.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for each number, how many others are strictly smaller? Values are only 0..100, which is the hint for a faster way.
Why this works: count how often each value appears, then a running total of those counts tells you "how many values are below v" for every v at once.
Example: nums = [8, 1, 2, 2, 3]
counts: 1→1, 2→2, 3→1, 8→1below 1 = 0, below 2 = 1, below 3 = 3, below 8 = 4answer: 8→4, 1→0, 2→1, 2→1, 3→3 → [4, 0, 1, 1, 3]
✦Hints open one at a time
↗Approach
Build a frequency array of size 101, then turn it into a prefix count where less[v] = number of elements with value below v. Each answer is a lookup. This trades a tiny fixed array for going from O(n²) to O(n + 101).
</>Solution (Java)
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] freq = new int[102];
for (int x : nums) freq[x + 1]++; // shift by one so freq[v] ends as "count of values < v"
for (int v = 1; v < freq.length; v++) freq[v] += freq[v - 1];
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i++) ans[i] = freq[nums[i]];
return ans;
}
}!Common mistake
Using the prefix count including v itself, which also counts equal elements. Use the total of values strictly less than v.
- Time: O(n + R) where R = 101 is the value range.
- Space: O(R).
