Sliding Window Maximum —
Monotonic deque. O(n) always.
Find the maximum in every sliding window of size k. Brute force rechecks the whole window each slide — O(n·k). A monotonic deque maintains a decreasing sequence of useful candidates and answers every window in O(1). Watch elements enter and leave the deque on LearnBug and the trick becomes completely clear.
What is the problem?
Given an array and window size k, return the maximum element of every contiguous subarray of size k as the window slides from left to right. For [1, 3, -1, -3, 5, 3, 6, 7] with k=3, the result is [3, 3, 5, 5, 6, 7]. The deque stores indices of elements in decreasing order of value — the front always holds the current window's maximum.
Why the deque is the right tool
A deque (double-ended queue) lets you add and remove from both ends in O(1). We need to remove stale elements from the front (out of window) and remove smaller elements from the back (useless — a larger element just arrived). On LearnBug you watch the deque shrink from the back as large elements arrive and shrink from the front as the window slides past old indices.
Array [1, 3, -1, -3, 5, 3, 6, 7] with k=3
Deque stores indices in decreasing order of their values. Front = current max index.
i=0 (val=1) — push index 0
Deque empty. Push 0. Window not full yet (need k=3 elements).
i=1 (val=3) — 3 > 1, pop index 0, push index 1
Index 0 (val=1) is smaller than new val 3 — it can never be a max while 3 is in the window. Pop it from back. Push 1.
i=2 (val=-1) — -1 < 3, just push. Window full → output max
-1 is smaller than 3 so push without popping. Window [1,3,-1] is now full. Max = nums[deque[0]] = nums[1] = 3. Append to result.
i=3 (val=-3) — push. Check front: index 1 still in window. Max = 3
-3 smaller than -1, push. Front index 1 is within window [i-k+1, i] = [1,3] ✓. Max = nums[1] = 3.
i=4 (val=5) — pops all! 5 is bigger than everything in deque
5 > -3, -1, 3 — pop indices 3, 2, 1 from back. Push 4. Max = nums[4] = 5.
i=5,6,7 — finish remaining windows
i=5 (val=3): 3 < 5, push 5. Front=4 in window. Max=5.
i=6 (val=6): pops 5 and 3, push 6. Max=6.
i=7 (val=7): pops 6, push 7. Max=7. Done.
Monotonic deque implementation
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing by value
result = []
for i in range(len(nums)):
# remove indices outside current window from front
if dq and dq[0] < i - k + 1:
dq.popleft()
# remove smaller elements from back — they're useless
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# window is full — record max (front of deque)
if i >= k - 1:
result.append(nums[dq[0]])
return resultTime & Space Complexity
Frequently asked questions
Why do we remove smaller elements from the back?
If element A is smaller than the new element B, and B arrives after A, then whenever A is in the window so is B — and B is larger. So A can never be the window maximum. It's useless and we remove it immediately. This is what keeps the deque monotonically decreasing.
Why check the front for expiry?
The front holds the index of the current maximum. As the window slides right, old indices fall outside the window. We check if dq[0] < i - k + 1 — if true, that index is no longer in the current window and we popleft it. This is why we store indices rather than values.
What is a deque and why not use a regular list?
A deque (double-ended queue) supports O(1) append and pop from both ends. A regular Python list has O(n) pop from the front (list.pop(0) shifts all elements). Since we need popleft in O(1), collections.deque is the correct data structure here.
What is the LeetCode problem for this?
LeetCode 239 — Sliding Window Maximum. Considered a hard problem because the deque approach is non-obvious. Once you understand the monotonic deque pattern, it extends to other problems: LC 862 (Shortest Subarray with Sum at Least K) and LC 1438 (Longest Continuous Subarray with Absolute Diff ≤ Limit).
How is this different from the sliding window technique?
The basic sliding window tracks a running sum or count with two pointers. Sliding window maximum is harder — you need the maximum, not just the sum, and maximum doesn't update incrementally when you remove the leftmost element. The deque solves this by maintaining the maximum candidate pool across the window.
Watch the deque update at every window position
Paste your array into LearnBug and see every enqueue and dequeue in the monotonic deque step by step.