What is the time complex for this solution with python heapq ?


  • 0
    T
    class Solution:
    
    def maxSlidingWindow(self, nums, k):
        heap, counter, answer = [], collections.Counter(), []
        for idx, n in enumerate(nums):
            heapq.heappush(heap, -n)
            counter[n] += 1
            if idx >= k - 1:
                while counter[-heap[0]] == 0:
                    heapq.heappop(heap)
                answer.append(-heap[0])
                counter[nums[idx - k + 1]] -= 1
        return answer

  • 1

    I think O(n log n), even for k=2. Consider a case where nums alternates between 2**30 and random smaller numbers, followed by a few -1 elements:

    n = 10000
    k = 2
    nums = [random.randrange(2**30) if i%2 else 2**30
            for i in range(n)]
    nums += [-1] * 3
    print Solution().maxSlidingWindow(nums, k)
    

    The window always contains a 2**30 and that's the overall largest number, so it blocks any popping until the very end, where everything but the three -1 elements will be popped. So you build up a heap with ~n elements, and then popping them all takes O(n log n), I think.


Log in to reply
 

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