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

• ``````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)
counter[nums[idx - k + 1]] -= 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.

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