How Many Numbers Are Smaller Than the Current Number
Problem
You are given an array nums whose values all lie between 0 and 100. For each element nums[i], report how many elements of the array (at any other index) are strictly smaller than it. Return these counts as an array aligned with the input.
The small value range is the whole trick: instead of comparing every pair, count how often each value 0..100 appears, then a prefix sum over the buckets tells you, for every value v, exactly how many numbers are below it.
nums = [8, 1, 2, 2, 3][4, 0, 1, 1, 3]def smaller_numbers_than_current(nums):
count = [0] * 101
for x in nums:
count[x] += 1
smaller = [0] * 101
running = 0
for v in range(101):
smaller[v] = running
running += count[v]
return [smaller[x] for x in nums]function smallerNumbersThanCurrent(nums) {
const count = new Array(101).fill(0);
for (const x of nums) count[x]++;
const smaller = new Array(101).fill(0);
let running = 0;
for (let v = 0; v <= 100; v++) {
smaller[v] = running;
running += count[v];
}
return nums.map(x => smaller[x]);
}int[] smallerNumbersThanCurrent(int[] nums) {
int[] count = new int[101];
for (int x : nums) count[x]++;
int[] smaller = new int[101];
int running = 0;
for (int v = 0; v <= 100; v++) {
smaller[v] = running;
running += count[v];
}
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i++) ans[i] = smaller[nums[i]];
return ans;
}vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
int count[101] = {0};
for (int x : nums) count[x]++;
int smaller[101] = {0};
int running = 0;
for (int v = 0; v <= 100; v++) {
smaller[v] = running;
running += count[v];
}
vector<int> ans;
for (int x : nums) ans.push_back(smaller[x]);
return ans;
}Explanation
The obvious solution compares every element against every other element — O(n²) pairs. The key insight is hidden in the constraints: every value sits in the tiny range 0..100. Whenever the value universe is that small, you can trade comparisons for counting.
First pass: build a frequency table. count[v] is a bucket (an array used as a hash map with the value as the key) holding how many times v appears in nums. For [8, 1, 2, 2, 3] this gives count[1]=1, count[2]=2, count[3]=1, count[8]=1.
Second pass: a prefix sum over the buckets. The number of elements strictly smaller than v is the total count of all buckets below v, so we sweep v from 0 to 100 keeping a running total: record smaller[v] = running before adding count[v]. In the example the sweep produces smaller[1]=0, smaller[2]=1, smaller[3]=3, smaller[8]=4.
Third pass: each answer is now a direct lookup — ans[i] = smaller[nums[i]]. For nums[0]=8 we read smaller[8]=4; for the two 2s we read smaller[2]=1 twice. Duplicates cost nothing extra because they share a bucket, which is exactly why the strictly-smaller rule works out: a value never counts its own bucket.
Each pass touches either the n elements once or the 101 buckets once, so the total work is O(n + k) with k = 101 — effectively linear, and the two fixed-size arrays make the extra space O(k), effectively constant. Compare that with O(n log n) for a sorting-based approach.