Leetcode: 315. Count of Smaller Numbers After Self

Pattern: Answer query on sorted data.
Can we break-down the problem in small and easily to solve parts? Suppose we are processing the element \(i\) from right to left, if we keep element \(nums[i+1,...,n-1]\) sorted, the problem becomes finding the right-most index where we could add \(nums[i]\) to the sorted list while keeping it sorted. Time complexity is \(O(n \log n)\) and space is \(O(n)\).

from typing import List
from sortedcontainers import SortedList


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        right = SortedList([])
        N = len(nums)
        ans = [0] * N
        for i in range(N - 1, -1, -1):
            j = right.bisect_left(nums[i])
            ans[i] = j
            right.add(nums[i])
        return ans


assert Solution().countSmaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert Solution().countSmaller([-1]) == [0]
assert Solution().countSmaller([-1, -1]) == [0, 0]