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] <= 100In 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the sorted copy and the result.
| 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. |
Numbers Smaller than current Number (LeetCode 1365) | Full solution with examples | Study Algorithms • Nikhil Lohia • 18,562 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