0019 - Sliding Window Maximum

You are given an array of integers nums and an integer k. There is a sliding window of size k that starts at the left edge of the array. The window slides one position to the right until it reaches the right edge of the array.

Return a list that contains the maximum element in the window at each step.

Example 1:

• Time Complexity - O(n * n)
• Space Complexity - O(n)

In [15]:

def maxSlidingWindow(nums,k):
    res=[0]*(len(nums)-k+1)
    window=nums[0:k]
    l=0
    res[l]=max(window)
    for r in range(k,len(nums)): 
        window.append(nums[r])
        window[l]=float("-inf")
        l+=1
        res[l]=max(window)
    return res

In [16]:

maxSlidingWindow([1,2,1,0,4,2,6], 3)

Out[16]:

[2, 2, 4, 4, 6]

https://youtu.be/DfljaUwZsOk?si=ffJvxcEXqyJFYCY4

• Time Complexity - O(n)
• Space Complexity - O(n)

The key thing to remember is:

• The deque stores INDICES, not values
• Step 1 - while right most element in queue is less than new element then continue to pop it.
• Step 2 - add new index to queue
• Step 3 - if left index (left border of window) > left most element in queue then pop from left of queue.
• Step 4 - if window length (r-l+1)>=k then append max to res array and slide the queue (l+=1)

In [5]:

from collections import deque 
def maxSlidingWindow2(nums,k):
    q=deque()
    l=r=0
    res=[]
    while r<len(nums):
        while q and nums[q[-1]]<nums[r]:
            q.pop()
        q.append(r)
        if l>q[0]:
            q.popleft()
        if r-l+1>=k:
            res.append(nums[q[0]])
            l+=1
        r+=1
    return res

In [6]:

maxSlidingWindow2([1,2,1,0,4,2,6], 3)

Out[6]:

[2, 2, 4, 4, 6]