How Many Numbers Are Smaller Than the Current Number — LeetCode 1365 Python Solution

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

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