Nlogn Python solution, binary indexed tree, 160 ms


  • 7
    K

    First get rank, the smallest number will be rank 1, the second smallest will be rank 2...With this rank info binary indexed tree can be used to count smaller numbers as we scan from right to left.

    def countSmaller(self, nums):
        rank, N, res = {val: i + 1 for i, val in enumerate(sorted(nums))}, len(nums), []
        BITree = [0] * (N + 1)
        
        def update(i):
            while i <= N:
                BITree[i] += 1
                i += (i & -i)
            
        def getSum(i):
            s = 0
            while i:
                s += BITree[i]
                i -= (i & -i)
            return s
        
        for x in reversed(nums):
            res += getSum(rank[x] - 1),
            update(rank[x])
        return res[::-1]
    

  • 0
    Z

    This is really cool. Thank you for sharing


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.