Sliding Window Maximum

Intuition

A brute-force scan of every window costs O(n*k) because it re-examines overlapping elements. The key observation is that if a newer element is greater than or equal to older elements still inside the window, those older elements can never be the maximum again and are safe to discard. We store indices in a deque and keep the corresponding values in decreasing order from front to back. That way the front always holds the index of the current window's maximum, and each index is pushed and popped at most once. The window boundary is enforced by evicting the front when its index falls outside the current range.

Algorithm walkthrough

1. 1Create an empty deque that will hold array indices, and an empty result list.
2. 2For each index i, pop indices from the back while nums at the back is less than or equal to nums[i]; those values can no longer be a maximum.
3. 3Push the current index i onto the back of the deque.
4. 4If the front index is out of the window (front <= i - k), remove it from the front.
5. 5Once i reaches k - 1, the first full window exists, so append nums at the front index to the result.
6. 6Return the result list after the loop finishes.

Implementation

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()  # stores indices; values are decreasing front-to-back
        result = []
        for i, num in enumerate(nums):
            # Drop smaller-or-equal values from the back
            while dq and nums[dq[-1]] <= num:
                dq.pop()
            dq.append(i)
            # Drop the front if it slid out of the window
            if dq[0] <= i - k:
                dq.popleft()
            # Record the max once the first window is complete
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result