How Many Numbers Are Smaller Than the Current Number Solution
How Many Numbers Are Smaller Than the Current Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
How Many Numbers Are Smaller Than the Current Number is an easy coding problem on arrays, hash table and counting sort, asked in Amazon, Google and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Counting Sort
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the array nums, for each nums[i] count how many numbers in the array are strictly smaller than it.
Return the answer as an array in the same order as the input.
Example 1
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: For 8 there are four smaller values; for 1 there are none; for each 2 only the 1 is smaller.
Example 2
Input: nums = [6,5,4,8]
Output: [2,1,0,3]
Example 3
Input: nums = [7,7,7,7]
Output: [0,0,0,0]
Explanation: Strictly smaller, so equal values do not count.
Constraints
1 <= nums.length <= 400 <= nums[i] <= 100
Follow-up: The values are bounded by 100. Can you answer every query in O(1) after O(n + 100) preprocessing?
Hints for How Many Numbers Are Smaller Than the Current Number
Hint 1
The nested-loop count is O(n²) and passes at this size, but the bounded range invites something better.
Hint 2
Tally how many times each value 0…100 occurs, then take a prefix sum of those tallies.
Hint 3
prefix[v - 1]is then exactly how many elements are strictly belowv.
How to solve How Many Numbers Are Smaller Than the Current Number
Values are bounded by 100, so tally them and take a prefix sum: prefix[v] then equals the number of elements strictly below v.
Approach
- Tally with an offset:
count[x + 1] += 1. - Prefix-sum the tally so
count[v]holds how many values are< v. - Map each
xtocount[x].
Why it works
After the shift, count[v] sums the frequencies of 0..v-1, which is precisely the count of strictly smaller elements.
Complexity
- Time —
O(n + 100) - Space —
O(100)
Pitfalls
- The
+ 1offset is what makes the comparison strict; without it you count<=. - The
O(n²)double loop passes but is not the intended solution.
Reference solution
Python
def smallerNumbersThanCurrent(nums):
count = [0] * 102
for x in nums:
count[x + 1] += 1
for v in range(1, 102):
count[v] += count[v - 1]
return [count[x] for x in nums]Java
public static int[] smallerNumbersThanCurrent(int[] nums) {
int[] count = new int[102];
for (int x : nums) count[x + 1]++;
for (int v = 1; v < 102; v++) count[v] += count[v - 1];
int[] out = new int[nums.length];
for (int i = 0; i < nums.length; i++) out[i] = count[nums[i]];
return out;
}C++
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> count(102, 0);
for (int x : nums) count[x + 1]++;
for (int v = 1; v < 102; v++) count[v] += count[v - 1];
vector<int> out;
for (int x : nums) out.push_back(count[x]);
return out;
}JavaScript
var smallerNumbersThanCurrent = function(nums) {
const count = new Array(102).fill(0);
for (let i = 0; i < nums.length; i++) count[nums[i] + 1]++;
for (let v = 1; v < 102; v++) count[v] += count[v - 1];
const out = [];
for (let i = 0; i < nums.length; i++) out.push(count[nums[i]]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets