Problem statement

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

Solution

Start from the last number and keep numbers in BST (in python it is SortedList). Then when we see new number we need to find how many elements in this list smaller than this number, and then put this number into our sorted list.

Complexity

Complexity of both operations : add to list and do binary search with bisect_left is O(log n), so overall complexity is O(n log n).

Code

from sortedcontainers import SortedList

class Solution:
    def countSmaller(self, nums):
        SList, ans = SortedList(), []
        for num in nums[::-1]:
            ind = SortedList.bisect_left(SList, num)
            ans.append(ind)
            SList.add(num)
            
        return ans[::-1]

Remark

In this type of problems there is often solutions using segment tree or BIT: the idea is to for each number get its order statistics, that is what will be the place if we sort. For example, if we have 3,1,4,5,2, then we create [0,0,0,0,0] array, then we meet number 3 first, so we update it like [0,0,1,0,0], then we have [1,0,1,0,0], then we have [1,0,1,1,0], [1,0,1,1,1], [1,1,1,1,1]. Instead of keeping list, what we keep is Segment Tree or BIT for quick answers for ranges: actually what we want to evaluate on each step is sum of elements in some range [0, ind]. Complexity of these approaches will be O(n log n) as well.