Sliding Window Maximum

Given an array and window size k, return the maximum of every length-k window as it slides one step at a time. A naive re-scan is O(nk); the deque solves it in O(n).

The key insight: maintain a deque of indices whose values are strictly decreasing. The front holds the current window's maximum. When the machine adds a new element, it pops indices from the back whose values are smaller or equal — they can never be a maximum again while this larger element is in the window. It also pops the front if that index has slid out of the window. The invariant keeps the deque ordered by both position and value.

Approach in steps:

1. For each index i, pop from the back while nums[back] <= nums[i].
2. Pop the front while front <= i - k (out of window).
3. Push i; once i >= k - 1, record nums[front].

from collections import deque
 
def maxSlidingWindow(nums, k):
    dq = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Time is O(n) — every index is pushed and popped at most once; space O(k).

Trickiest edge case: k = 1 and duplicate-heavy windows. With k = 1, the max is the element itself and the out-of-window check fires every step. With equal values, the <= in the back-pop means the newer equal element wins — correct, since it lives longer in the window.