159 ms Python solution with Binary Indexed Tree


  • 0
    Y
        def countSmaller(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if len(nums)==0:
                return []
            minimum = min(nums)
            nums = map(lambda x:x-minimum+1,nums)
            maximum = max(nums)                 #Normalize the array to make it fit binary indexed tree.
            BIT = {}                            #{num:count}
            answer = []
            for num in nums[::-1]:
                idx,count = num-1,0
                while idx>0:
                    if idx in BIT:
                        count += BIT[idx]
                    idx -= idx&(-idx)
                while num<=maximum:
                    if num not in BIT:
                        BIT[num] = 1
                    else:
                        BIT[num] += 1
                    num += num&(-num)
                answer.append(count)
            return answer[::-1]
    

Log in to reply
 

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