Problem description:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

1
2
3
4
5
6
7
Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are2 smaller elements (2 and 1).
To the right of 2 there is only1 smaller element (1).
To the right of 6 there is1 smaller element (1).
To the right of 1 there is0 smaller element.

Example 2:

1
2
Input: nums = [-1]
Output: [0]

Example 3:

1
2
Input: nums = [-1,-1]
Output: [0,0]

Constraints:

  • 1 <= nums.length <= 105
  • 104 <= nums[i] <= 104

Solution:

create a sorted list to help count the smaller number
traverse starting from right
use bisect_left to find position to insert in the sorted list, that would be number of smaller element after this item.
bisect_insort to insert the item in sorted order

1
2
3
4
5
6
7
8
9
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        result = []
        sorted_list = []
        for num in nums[::-1]:
            pos = bisect_left(sorted_list, num)
            result.append(pos)
            bisect.insort(sorted_list, num)
        return result[::-1]

time complexity: $O()$
space complexity: $O()$
reference:
related problem: