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.
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; }}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.