Q28: Sliding Window Maximum. - DSA Patterns (Multi-Lang)

In Simple Words: Use a Monotonic Deque storing indices in decreasing value order. Front is always maximum of current window. Pop smaller elements from back before inserting, pop out-of-window elements from front.

Time: $O(N)$ | Space: $O(K)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    q = deque()  # stores indices
    res = []
    for i in range(len(nums)):
        # Pop out of window
        if q and q[0] <= i - k:
            q.popleft()
        # Maintain decreasing order
        while q and nums[q[-1]] < nums[i]:
            q.pop()
        q.append(i)
        if i >= k - 1:
            res.append(nums[q[0]])
    return res