How Many Numbers Are Smaller Than the Current Number
EasyPrompt
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
Example 1:
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).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]
Constraints:
2 <= nums.length <= 5000 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward method. We iterate through the array for each element and compare it with every other element to count how many are smaller.
Algorithm
- Initialize a result array
answith the same length asnums. - Loop through each element
nums[i]fromi = 0ton-1. - For each
nums[i], initialize acountto 0. - Start a nested loop for each element
nums[j]fromj = 0ton-1. - Inside the nested loop, if
j != iandnums[j] < nums[i], increment thecount. - After the inner loop, assign the final
counttoans[i]. - Return the
ansarray.
Walkthrough
The brute force approach involves using nested loops. The outer loop picks an element nums[i], and the inner loop iterates through all elements nums[j] in the array.
For each nums[i], we initialize a counter. Inside the inner loop, we check if j is not equal to i and if nums[j] is smaller than nums[i]. If both conditions are true, we increment the counter.
After the inner loop completes, the counter holds the total number of elements smaller than nums[i]. We store this count in our result array at the corresponding index i.
This process is repeated for every element in the input array.
class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int n = nums.length; int[] ans = new int[n]; for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < n; j++) { if (i != j && nums[j] < nums[i]) { count++; } } ans[i] = count; } return ans; }}Complexity
Time
O(N^2), where N is the number of elements in the input array. This is because for each of the N elements, we iterate through the entire array again, leading to N * N comparisons.
Space
O(N) to store the output array. If the output array is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires no extra data structures besides the result array.
Cons
Inefficient for large inputs due to its quadratic time complexity.
A more optimized approach involves sorting. By sorting a copy of the array, we can determine the count of smaller numbers for any given value by finding its first index in the sorted array. A hash map can be used to store these counts for efficient lookup.
Algorithm
- Create a copy of the
numsarray, namedsortedNums. - Sort the
sortedNumsarray in ascending order. - Create a
HashMapto store the mapping from a number to the count of smaller numbers. - Iterate through the
sortedNumsarray. For each number, if it's not already in the map, add the number as the key and its index as the value. This works because the index of the first occurrence of a number in a sorted array is equal to the count of elements smaller than it. - Initialize a result array
ans. - Iterate through the original
numsarray. For eachnum, get its corresponding count from the map and store it inans. - Return the
ansarray.
Walkthrough
This method improves upon the brute-force approach by avoiding repeated scans. First, we create a copy of the input array nums and sort it. Let's call the sorted copy sortedNums.
The number of elements smaller than a certain value x is simply the index of the first occurrence of x in sortedNums. For example, in the sorted array [1, 2, 2, 3, 8], the first 2 is at index 1, meaning one number is smaller than it.
To efficiently retrieve this count for each number in the original nums array, we can pre-process the sortedNums array. We iterate through sortedNums and store the first index of each unique number in a hash map. The map will store (number, count_of_smaller_numbers).
Finally, we iterate through the original nums array one last time. For each nums[i], we look up its value in the hash map to get the count of smaller numbers and place it in our result array.
import java.util.Arrays;import java.util.HashMap;import java.util.Map; class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int n = nums.length; int[] sortedNums = Arrays.copyOf(nums, n); Arrays.sort(sortedNums); Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { map.putIfAbsent(sortedNums[i], i); } int[] ans = new int[n]; for (int i = 0; i < n; i++) { ans[i] = map.get(nums[i]); } return ans; }}Complexity
Time
O(N log N), where N is the number of elements. The dominant operation is sorting the array. Populating the map and the final result array both take O(N) time.
Space
O(N) to store the copy of the array and the hash map. The space for the result array is also O(N).
Trade-offs
Pros
Significantly more efficient than the brute-force approach for larger N.
Conceptually clear, leveraging a standard sorting algorithm.
Cons
Requires extra space for the sorted copy and the hash map.
Not the most optimal if the range of numbers is small and known.
The most efficient approach leverages the problem's constraint that numbers are in a small, fixed range (0-100). We can use a frequency array (or counting sort idea) to count occurrences of each number and then use prefix sums to find the number of smaller elements for each value in O(1) time.
Algorithm
- Create a frequency array
countsof size 101 (for values 0-100) and initialize it with zeros. - Iterate through the input
numsarray and populate thecountsarray:counts[num]++. - Create a prefix sum array, let's call it
smallerCounts, also of size 101. - Calculate the prefix sums:
smallerCounts[0] = 0, and forifrom 1 to 100,smallerCounts[i] = smallerCounts[i-1] + counts[i-1]. - Initialize the result array
ans. - Iterate through the original
numsarray. For eachnum = nums[i], setans[i] = smallerCounts[num]. - Return the
ansarray.
Walkthrough
Given the constraint 0 <= nums[i] <= 100, we can use an array as a frequency map. We create an integer array counts of size 101, initialized to all zeros.
We iterate through the input nums array once. For each number num, we increment counts[num]. After this pass, counts[i] will hold the frequency of the number i in the input array.
Next, we transform the counts array to store the number of elements smaller than the index. We can do this by calculating a running sum (prefix sum). Let's say we have a new array smallerCounts. smallerCounts[0] is 0 (no numbers are smaller than 0). For i > 0, smallerCounts[i] is the sum of all frequencies of numbers from 0 to i-1. This can be calculated iteratively: smallerCounts[i] = smallerCounts[i-1] + counts[i-1].
After computing the prefix sums, smallerCounts[x] directly gives us the count of numbers in the original array that are strictly smaller than x.
Finally, we iterate through the original nums array again. For each nums[i], we find the answer by looking up smallerCounts[nums[i]] and store it in the result array.
class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { // Constraints: 0 <= nums[i] <= 100 int[] counts = new int[101]; for (int num : nums) { counts[num]++; } // Calculate prefix sum for smaller counts int[] smallerCounts = new int[101]; smallerCounts[0] = 0; for (int i = 1; i < 101; i++) { smallerCounts[i] = smallerCounts[i-1] + counts[i-1]; } int[] ans = new int[nums.length]; for (int i = 0; i < nums.length; i++) { ans[i] = smallerCounts[nums[i]]; } return ans; }}Complexity
Time
O(N + K), where N is the length of `nums` and K is the range of possible values (101). Since K is a constant, the complexity is linear, O(N).
Space
O(K + N). We use an array of size K for frequency counts and prefix sums, and an array of size N for the result. Since K is constant (101), this simplifies to O(N).
Trade-offs
Pros
Most efficient solution with linear time complexity.
Perfectly suited for problems with a small and fixed range of input values.
Cons
Space complexity depends on the range of numbers (K). It would be inefficient if the range of numbers were very large.
Solutions
Solution
class Solution {public int[] smallerNumbersThanCurrent(int[] nums) { int[] arr = nums.clone(); Arrays.sort(arr); for (int i = 0; i < nums.length; ++i) { nums[i] = search(arr, nums[i]); } return nums; }private int search(int[] nums, int x) { int l = 0, r = nums.length; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l; }}class Solution {public: vector<int> smallerNumbersThanCurrent(vector<int> &nums) { vector<int> arr = nums; sort(arr.begin(), arr.end()); for (int i = 0; i < nums.size(); ++i) { nums[i] = lower_bound(arr.begin(), arr.end(), nums[i]) - arr.begin(); } return nums; }};class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: arr = sorted(nums) return [bisect_left(arr, x) for x in nums]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.