Problem Description

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max of the sliding window.

Example 1:

  • Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
  • Output: [3,3,5,5,6,7]
  • Explanation:
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

  • Input: nums = [1], k = 1
  • Output: [1]

My Idea

The initial idea was simply to check for the max element in each window and add it to the resulting list. This yielded a time complexity of O(n*k), which was not fast enough for a submission. The improved algorithm utilizes a double ended queue to implement a monotonic decreasing queue. If the new value added to the window is larger than the stored values we remove them, since they can never be max. Once we’ve filled the window we append the leftmost element of the queue to the result list, since this is the current max and move our l pointer. This yields the slightly better time complexity of O(n), which was enough for the submission.

My solution

# Time Complexity: O(n)
from collections import deque
def maxSlidingWindow(nums:list[int], k:int) -> list[int]:
    l = 0
    res = []
    q = deque()

    for r in range(len(nums)):
        while q and nums[q[-1]]<nums[r]:
            q.pop()
        q.append(r)

        if l > q[0]:
            q.popleft()

        if (r+1) >= k:
            res.append(nums[q[0]])
            l+=1

    return res

# Initial idea O(n*k)
def maxSlidingWindowInitial(nums:list[int], k:int) -> list[int]:
    l=0
    res=[]
    for r in range(k,len(nums)+1):
        res.append(max(nums[l:r]))
        l+=1

    return res