Problem statement

https://binarysearch.com/problems/Long-Distance/

Solution

Equal to Leetcode 0315. Count of Smaller Numbers After Self

Complexity

It is O(n log n) for time and O(n) for space.

Code

from sortedcontainers import SortedList

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