Sliding Window Maximum

The problem

You are given an array nums and a sliding window of size k. Return the max in each window.

Function: def maxSlidingWindow(nums,k):

Example input (a JSON list of arguments): [[1, 3, -1, -3, 5, 3, 6, 7], 3]
Expected output: [3, 3, 5, 5, 6, 7]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Keep candidate indices in decreasing value order in a deque.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def maxSlidingWindow(nums,k):
    queue=deque();out=[]
    for i,n in enumerate(nums):
        while queue and queue[0]<=i-k:queue.popleft()
        while queue and nums[queue[-1]]<=n:queue.pop()
        queue.append(i)
        if i>=k-1:out.append(nums[queue[0]])
    return out

Why it works

Keep candidate indices in decreasing value order in a deque. Expire indices outside the window and discard smaller trailing candidates before adding each new index; the front is the maximum.

Complexity: O(n) time / O(k) space.

Time: O(n) time · Space: O(k) space