Sliding Window Maximum seems straightforward: find the max in each window. But 4 common mistakes cause most solutions to fail.
This guide shows you the exact bugs and how to fix them permanently.
The 4 mistakes:
< i - k instead of < i - k + 1)popleft())Quick fixes:
from collections import deque
dq = deque() # Not stack!
# Remove out-of-window
while dq and dq[0] < i - k + 1: # Correct boundary
dq.popleft() # Remove from front
# Add result only when window is full
if i >= k - 1:
result.append(nums[dq[0]])❌ Wrong:
def maxSlidingWindow(nums, k):
result = []
stack = [] # WRONG: Can't remove from front!
for i in range(len(nums)):
# How to remove out-of-window elements?
# stack.pop() only removes from top!
# ...Sliding window needs to remove from BOTH ends:
Stack only supports one end!
✅ Correct:
from collections import deque
def maxSlidingWindow(nums, k):
result = []
dq = deque() # CORRECT: Can remove from both ends
for i in range(len(nums)):
# Remove from front: O(1)
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove from back: O(1)
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result❌ Wrong:
# Wrong boundary check
while dq and dq[0] < i - k: # Off by one!
dq.popleft()Window of size k at position i:
i - k + 1i< i - k + 1Visual:
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
At i=3 (processing -3):
Window: [i-k+1, i] = [1, 3]
Indices: 1, 2, 3
Values: 3, -1, -3
Out of window: index < 1
Correct check: dq[0] < 3 - 3 + 1 = 1
Wrong check: dq[0] < 3 - 3 = 0 (keeps index 0!)✅ Correct:
while dq and dq[0] < i - k + 1: # Correct boundary
dq.popleft()❌ Wrong:
# Forgot to remove out-of-window elements!
for i in range(len(nums)):
# Missing: while dq and dq[0] < i - k + 1: ...
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])Result: Deque contains elements outside current window, wrong maximum.
✅ Correct:
for i in range(len(nums)):
# MUST remove out-of-window first
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])❌ Wrong:
for i in range(len(nums)):
# ...
dq.append(i)
# WRONG: Adds result before window is full
result.append(nums[dq[0]])Result: First k-1 results are wrong (window not full yet).
✅ Correct:
for i in range(len(nums)):
# ...
dq.append(i)
# CORRECT: Only add when window is full
if i >= k - 1:
result.append(nums[dq[0]])Why i >= k - 1?
from collections import deque
def maxSlidingWindow(nums, k):
"""
LeetCode #239: Sliding Window Maximum
Time: O(n)
Space: O(k)
"""
if not nums or k == 0:
return []
if k == 1:
return nums
result = []
dq = deque() # Store indices, maintain decreasing order
for i in range(len(nums)):
# 1. Remove out-of-window elements
while dq and dq[0] < i - k + 1:
dq.popleft()
# 2. Remove smaller elements (they'll never be max)
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
# 3. Add current element
dq.append(i)
# 4. Add to result only when window is full
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Test
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# Output: [3, 3, 5, 5, 6, 7]nums = [1, 2, 3], k = 1
# Every element is its own window max
# Output: [1, 2, 3]nums = [1, 2, 3], k = 3
# Single window containing all elements
# Output: [3]nums = [3, 3, 3, 3], k = 2
# Output: [3, 3, 3]dq[0] < i - k + 1?
i >= k - 1?
The 4 fixes:
from collections import deque< i - k + 1dq.popleft()if i >= k - 1The template:
from collections import deque
dq = deque()
for i in range(len(nums)):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])Next steps:
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free