Watch 10 video solutions for How Many Numbers Are Smaller Than the Current Number, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by Nikhil Lohia has 24,031 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100Problem Overview: You receive an integer array nums. For each element, compute how many numbers in the array are strictly smaller than it. The output is another array where result[i] equals the count of values less than nums[i].
Approach 1: Brute Force Comparison (O(n^2) time, O(1) space)
The direct solution compares every element with every other element. For each index i, iterate through the entire array again and count how many values are smaller than nums[i]. This uses two nested loops and increments a counter whenever nums[j] < nums[i]. The logic is simple and requires no extra data structures beyond the output array. This approach is useful for understanding the problem constraints but becomes inefficient when n grows because the comparisons scale quadratically.
Approach 2: Sorting with Rank Mapping (O(n log n) time, O(n) space)
A faster method sorts the numbers and records the first index where each value appears. After sorting, the index of a number represents how many values are smaller than it. Traverse the sorted array and store the first occurrence of each number in a hash map so duplicates share the same count. Then iterate through the original array and replace each value with its mapped index. Sorting reduces the number of comparisons and the hash lookup provides constant‑time access for each element.
This approach combines sorting with a hash table to map values to their rank. The input array itself is still processed sequentially, which aligns naturally with typical array operations.
Recommended for interviews: Interviewers usually expect the sorting approach. The brute force version proves you understand the definition of the problem, but the sorted ranking technique demonstrates that you can reduce repeated comparisons using preprocessing. Mentioning how duplicates are handled with a hash map is often the key insight they want to hear.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n^2) | O(1) | Small arrays or when demonstrating the basic logic during interviews |
| Sorting with Rank Mapping | O(n log n) | O(n) | General case solution that avoids repeated comparisons and handles duplicates efficiently |