Sliding Window Maximum Solution

Problem

Given an array of integers and a window of size k, find the maximum value in each contiguous window as it slides one position at a time from left to right. Return all maximums in order.

For example, with nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3:

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation: The windows [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7] have maximums 3, 3, 5, 5, 6, 7.

Intuition

At each step we need the largest value among the k elements currently visible. Scanning all k elements per step works but repeats comparisons as the window moves. The key insight is that any element that is both older and smaller than a newer element can never be the maximum for any future window — the newer element will remain in range longer and is strictly larger. A monotonic deque tracks only the indices that could still be the maximum, so each window's answer is just a deque front lookup in O(1).

Approach 1 — Brute Force

For each of the n − k + 1 starting positions, scan the entire window to find its maximum.

Iterate start from 0 to len(nums) - k inclusive.
Find the maximum over nums[start : start + k].
Append that maximum to the result.

1def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
2    result = []
3    for start in range(len(nums) - k + 1):
4        result.append(max(nums[start:start + k]))
5    return result

Time: O(n·k) — each of the n−k+1 windows requires a full k-element scan.
Space: O(1) excluding the output array.

Approach 2 — Monotonic Deque

Maintain a deque of indices whose corresponding values are strictly decreasing from front to back. The front always holds the index of the current window's maximum.

Process each index i from 0 to n − 1.
Remove from the front any index that has slid outside the window (< i − k + 1).
Remove from the back any index whose value is less than nums[i] — it is permanently dominated and can never be a future maximum.
Push i onto the back.
Once i >= k − 1, record nums[deque.front()] as the current window's maximum.

1from collections import deque
2
3def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
4    result = []
5    dq = deque()  # stores indices; front always holds the current window max index
6
7    for i in range(len(nums)):
8        # remove indices that have slid out of the window
9        while dq and dq[0] < i - k + 1:
10            dq.popleft()
11
12        # remove back indices dominated by nums[i] — they can never be a future max
13        while dq and nums[dq[-1]] < nums[i]:
14            dq.pop()
15
16        dq.append(i)
17
18        if i >= k - 1:  # first full window is now complete
19            result.append(nums[dq[0]])
20
21    return result

Time: O(n) — each index is pushed and popped from the deque at most once across the entire pass.
Space: O(k) — the deque holds at most k indices at any moment.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n·k)	O(1)	Acceptable only when k is very small (≤ 5) or input is tiny
Monotonic Deque	O(n)	O(k)	The expected solution for any non-trivial input size

Common Mistakes

Storing values instead of indices in the deque — you need the actual position to check whether the front element has slid out of the window; a value alone gives you no way to make that check.
Off-by-one in the eviction condition — the left boundary of window i is i − k + 1, so the check is dq[0] < i − k + 1 (strict less-than); using <= incorrectly evicts a valid index sitting exactly on the boundary.
Emitting results before the first full window — output starts at i == k − 1, not at i == 0; adding earlier produces extra entries at the front of the result.
Forgetting to pop the back on equal values — using < (keep ties) is correct; the older equal index gives the right maximum until it leaves the window. Using <= (discard ties) is also correct and keeps the deque marginally smaller, so either works.
Reaching for a max-heap instead — a priority queue answers "what is the max" in O(log k) and cannot efficiently remove stale out-of-window entries; the monotonic deque is the right data structure here.

Sliding Window Maximum — Solution