How Many Numbers Are Smaller Than the Current Number: Sorting and Counting Pattern
Given an array nums, for each nums[i] you need to find how many numbers in the array are smaller than it. In other words, for each element, count the number of elements that are strictly less than it across the entire array. Return the counts as a new array.
This is LeetCode 1365: How Many Numbers Are Smaller Than the Current Number, an easy problem that teaches you how to combine sorting with a hash map to answer rank-style queries efficiently.
Why this problem matters
Counting how many elements are smaller than a given value is a fundamental operation that appears in many forms across algorithm problems. Ranking, percentile calculations, and relative ordering all reduce to this same idea: figure out where each element sits in the sorted order, then use that position as the answer.
The brute force solution compares every pair of elements, which takes O(n^2) time. That works for small inputs, but the sorting approach brings it down to O(n log n), which is a significant improvement. More importantly, the technique of building a rank map from a sorted copy of the array is a reusable pattern. Once you recognize it, you can apply it to dozens of similar problems.
This problem also reinforces the connection between sorting and hash maps. Sorting gives you the relative order. The hash map lets you look up that order in constant time. Together, they turn a quadratic comparison problem into a near-linear one.
The key insight
After sorting the array, the index of each value's first occurrence tells you exactly how many distinct smaller values exist. Here is the approach:
- Sort a copy of the array.
- Walk through the sorted copy and record each value's index the first time you see it. This index equals the count of values that are strictly smaller.
- Use a hash map to store these mappings for O(1) lookup.
- Iterate through the original array and look up each element's count from the hash map.
The reason the first-occurrence index works is that in a sorted array, everything to the left of a value is smaller than or equal to it. The first time a value appears, everything to its left is strictly smaller. So the index itself is the answer.
The solution
def smallerNumbersThanCurrent(nums):
sorted_nums = sorted(nums)
rank = {}
for i, v in enumerate(sorted_nums):
if v not in rank:
rank[v] = i
return [rank[v] for v in nums]
The first line creates a sorted copy of the input without modifying the original. Then you iterate through the sorted copy, and for each value, you record its index only if you have not seen that value before. This ensures duplicates get the same rank as their first occurrence, which is correct because the count of strictly smaller numbers is the same for all copies of the same value.
Finally, you build the result by looking up each original element in the rank map. Since hash map lookups are O(1), this final pass is linear.
The "first occurrence index in a sorted array equals the count of smaller elements" trick works whenever you need to rank elements. You will see this same idea in problems like Rank Transform of an Array and relative sort problems.
Visual walkthrough
Let's trace through nums = [8, 1, 2, 2, 3] step by step, from sorting to building the rank map to producing the final result.
Step 1: Start with the original array.
We need to find, for each element, how many numbers in the array are strictly smaller than it.
Step 2: Sort a copy of the array.
Sorting gives us [1, 2, 2, 3, 8]. The position of each value's first occurrence tells us how many values are smaller.
Step 3: Build a rank map from the sorted array.
Walk through the sorted array. For each value, record its index only the first time you see it. This gives: {1:0, 2:1, 3:3, 8:4}.
Step 4: Look up each original element in the rank map.
For each element in nums, look up its rank. The rank equals the count of smaller numbers. Result = [4, 0, 1, 1, 3].
Each element's rank in the sorted array directly answers the question "how many numbers are smaller?" The hash map makes lookups instant, so the total work is dominated by the sort.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Sort + hash map | O(n log n) | O(n) |
Time: Sorting takes O(n log n). Building the rank map is O(n). Looking up each element is O(n). The total is O(n log n), dominated by the sort.
Space: The sorted copy takes O(n) space. The hash map takes O(n) space in the worst case (all unique values). The result array takes O(n). Overall, O(n) additional space.
The building blocks
1. Sort-based ranking
sorted_nums = sorted(nums)
rank = {}
for i, v in enumerate(sorted_nums):
if v not in rank:
rank[v] = i
Sort the data, then walk through it to assign ranks. The first occurrence gets the index as its rank. This pattern appears in any problem where you need to convert values into their relative positions. It handles duplicates naturally because later occurrences of the same value are skipped.
2. Hash map for O(1) lookup
return [rank[v] for v in nums]
After computing ranks, store them in a hash map so you can answer queries in constant time. This is the same lookup pattern used in Two Sum (storing complements) and Group Anagrams (storing canonical forms). The hash map bridges the gap between "I computed the answer for each unique value" and "I need to map that answer back to every position in the original array."
Edge cases
- All elements identical
[7, 7, 7, 7]: every element has 0 smaller numbers. The sorted array is the same, and the first occurrence index is 0 for all. - Already sorted
[1, 2, 3, 4]: the result is[0, 1, 2, 3], matching the indices directly. - Reverse sorted
[4, 3, 2, 1]: the result is[3, 2, 1, 0]. Sorting still produces the correct rank map. - Single element
[5]: the result is[0]. No other elements exist, so the count is always zero. - Two elements, equal
[3, 3]: both get rank 0. Neither is strictly smaller than the other. - Large spread with duplicates
[1, 1, 100, 100]: result is[0, 0, 2, 2]. The two 1s each have 0 smaller, and the two 100s each have 2 smaller.
From understanding to recall
The sort-and-rank pattern is simple to understand when you read it. Sorting, building a hash map, looking up values. Nothing surprising. But under interview pressure, the details matter: remembering to check if v not in rank to handle duplicates, knowing that the first-occurrence index equals the count of smaller elements, and building the result with a list comprehension over the original array.
Spaced repetition helps you internalize these details so they become automatic. You practice writing the sort, the rank map construction, and the lookup from scratch. After a few repetitions at increasing intervals, you do not need to re-derive the approach. You see "count smaller elements" and the code flows out.
This sort-and-rank pattern is one of the reusable building blocks that CodeBricks drills independently. Once you have it down, you can apply it to ranking problems, percentile queries, and relative-order questions without hesitation.
Related posts
- Contains Duplicate - Hash set duplicate detection
- Two Sum - Hash map complement lookup
- Sort Colors - Dutch flag partitioning
- Counting Bits - Counting patterns with DP
- Rank Transform of an Array - Array ranking
CodeBricks breaks LeetCode 1365 into its sorting and hash map building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a counting or ranking question comes up in your interview, you do not think about it. You just write it.