172ms Python BITree solution beats 99.07%

  • 6

    The problem is equal to find each number's inversion count. Actually there are three kinds of solutions: BST, mergeSort, and BITree. While the first two answer's time complexity is O(nlogn), and BITree time comlexity is O( nlog(maximumNum) ).

    Looking for what is BITree?

    Actually we use the BITree to trace the total count of each position from [0-maximum] like a RadixSort. When we at index i, we want to find the smaller num's total count in range [i+1, n-1]. First, we find the maximum num in the array, and create a BITree length(maximum). After init, we could iterate the array from n-1 to 0, each time we could find the smaller num's total count using the BITree's sumRange function, add one to the num[i] position using BITree's update function. Each operation is O(log(maximum)), thus the total complexity will be O( n*log(maximumNum) ).

    Well, in this problem, there might be minus numbers in the array, we could add a padding num which equal to the minimum number in the array.

    Finally the code:

    class Solution(object):
        def getSum(self, T, idx):
            ans = 0
            while idx:
                ans += T[idx]
                idx -= idx & (-idx)
            return ans
        def update(self, T, idx, val):
            while idx <= len(T)-1:
                T[idx] += val
                idx += idx & (-idx)
        def countSmaller(self, nums):
            :type nums: List[int]
            :rtype: List[int]
            if not nums:
                return []
            n = len(nums)
            padding = min(nums)
            if padding <= 0:
                nums = [a + 1 - padding for a in nums]
            m = max(nums)
            T = [0] * (m+1)
            ans = []
            t = 0
            for num in nums[::-1]:
                ans.append(self.getSum(T, num-1))
                self.update(T, num, 1)
            return ans[::-1]

    BTW: This is my first time answer a question, and wish my poor English could explain that clearly. I'll be glad to receive your reply which including any grammar problem either. ^_^

  • 0

    Nice solution ! I have implement this idea with the C++ code . can you explain me how to deal with duplicate number cases ?

  • 0

    make sure you got that T[i] indicated for the total count of "i" appeared at current iteration

    3 3 2 2 1 1

    after the third iteration, T[1] will equal to 2 (1 appeared 2 times), and T[2] will equal to 1 (2 appeared 1 time)

    when at the 4th iteration, nums[2] = 2, so we using BIT to calculate the sum in range[0,2), which equals to 2

    when at the 5th iteration, nums[1] = 3, so we using BIT to calculate the sum in range[0,3), which equals to 4

    so all of the duplicate numbers have been calculated

  • 0

    Thanks a lot . I have fixed the problem.

  • 0

    it is a pretty nice method. But have you considered the case that max(nums) is very large, say, 2^31-1? Your list will be huge and likely will cause memory allocation error.

  • 0

    I had used a merge sort based algorithm before this method, and I found that in this particular problem there were lots of duplicated numbers in test case, so BITree based algorithm would have a better performance. If max(nums) is very large, that merge sort based(nlogn) solution will be better.

  • 0

    Actually, I can't agree that the time complexity is restrictly O(nlongn). In fact, the time complexity is not in P because it relies on a numeric value in the input.

Log in to reply

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