How Many Numbers Are Smaller Than the Current Number - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Brute Force Approach
In this approach, we simply iterate over the array for each element, comparing it with every other element to count how many numbers are smaller. This is a straightforward nested loop approach where the outer loop picks the current number and the inner loop counts numbers smaller than it.
This code uses two loops: the outer loop iterates through each element of the array nums, and the inner loop counts how many elements are less than the current element. The counts are stored in the result array.
Complexity
Time Complexity: O(n^2), where n is the number of elements in the array. Space Complexity: O(n) for the result array.
Approach 2: Optimal Sorting Approach
This approach uses sorting to achieve a more efficient solution. We sort a copy of the array while keeping track of the indices and then assign the number of lesser elements directly based on sorted positions.
This solution sorts a copy of the array to quickly count numbers less than each element. It uses qsort for efficiency.
Complexity
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the sorted copy and the result.
Approach 3: Sorting + Binary Search
We can make a copy of the array nums, denoted as arr, and then sort arr in ascending order.
Next, for each element x in nums, we can use binary search to find the index j of the first element that is greater than or equal to x. Then j is the number of elements that are smaller than x. We can store j in the answer array.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Counting Sort + Prefix Sum
We notice that the range of elements in the array nums is [0, 100]. Therefore, we can use the counting sort method to first count the number of each element in the array nums. Then we calculate the prefix sum of the counting array. Finally, we traverse the array nums. For each element x, we directly add the value of the element at index x in the counting array to the answer array.
The time complexity is O(n + M), and the space complexity is O(M). Where n and M are the length and the maximum value of the array nums, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the number of elements in the array. Space Complexity: O(n) for the result array. |
| Optimal Sorting Approach | Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the sorted copy and the result. |
| Sorting + Binary Search | — |
| Counting Sort + Prefix Sum | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Numbers Smaller than current Number (LeetCode 1365) | Full solution with examples | Study Algorithms • Nikhil Lohia • 25,340 views views
Watch 9 more video solutions →Frequently Asked Questions
Is How Many Numbers Are Smaller Than the Current Number easy or hard?
How Many Numbers Are Smaller Than the Current Number Python/Java solution
How to solve How Many Numbers Are Smaller Than the Current Number in O(n)?
What is the best approach for How Many Numbers Are Smaller Than the Current Number?
Is How Many Numbers Are Smaller Than the Current Number asked at Google/Amazon/Meta?
What data structure is used in How Many Numbers Are Smaller Than the Current Number?
What is the time complexity of How Many Numbers Are Smaller Than the Current Number?
Ready to solve this problem?
Practice How Many Numbers Are Smaller Than the Current Number with our built-in code editor and test cases.
Practice on FleetCode