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.
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.
Time Complexity: O(n^2), where n is the number of elements in the array. Space Complexity: O(n) for the result array.
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.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the sorted copy and the result.
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.
Python
Java
C++
Go
TypeScript
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
Numbers Smaller than current Number (LeetCode 1365) | Full solution with examples | Study Algorithms • Nikhil Lohia • 24,031 views views
Watch 9 more video solutions →Practice How Many Numbers Are Smaller Than the Current Number with our built-in code editor and test cases.
Practice on FleetCode