EasyNo. 1365
How Many Numbers Are Smaller Than the Current Number — LeetCode 1365 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, Counting Sort, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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].
Example
- 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).
Python solution
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
arr = sorted(nums)
return [bisect_left(arr, x) for x in nums]Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1365. How Many Numbers Are Smaller Than the Current Number is filed here because LeetCode tags it Sorting and Counting Sort, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1122 | Relative Sort Array | Easy |
| 1366 | Rank Teams by Votes | Medium |
| 0049 | Group Anagrams | Medium |
| 0169 | Majority Element | Easy |
| 0217 | Contains Duplicate | Easy |
| 0229 | Majority Element II | Medium |
Frequently asked questions
- How hard is LeetCode 1365. How Many Numbers Are Smaller Than the Current Number?
LeetCode 1365. How Many Numbers Are Smaller Than the Current Number is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1365. How Many Numbers Are Smaller Than the Current Number?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 1365. How Many Numbers Are Smaller Than the Current Number?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1365. How Many Numbers Are Smaller Than the Current Number cover?
LeetCode 1365. How Many Numbers Are Smaller Than the Current Number is tagged Array, Hash Table, Counting Sort and Sorting on LeetCode.