Sliding Window Maximum with Monotonic Deque
Maintain a decreasing deque of indices to answer maximum-in-window queries in O(1) per element, solving the sliding-window-maximum problem in O(n).
Sliding Window Maximum with Monotonic Deque is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Sliding Window Maximum Problem
The Sliding Window Maximum problem (LeetCode 239) gives an array and a window size k. As the window slides from left to right one position at a time, output the maximum element in each window. A brute-force approach computes the max of each k-element window in O(k) — giving O(nk) total, which is too slow for large k.
The monotonic deque (double-ended queue) solution achieves O(n) overall by maintaining a decreasing deque of indices. The front always holds the index of the current window's maximum, providing O(1) max queries while allowing both front and back operations.
from collections import deque
# Brute force O(nk) for comparison
def sliding_max_brute(nums, k):
return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print('Input:', nums, 'k=', k)
print('Expected: [3, 3, 5, 5, 6, 7]')
print('Brute: ', sliding_max_brute(nums, k))Monotonic Deque: The Key Idea
Maintain a monotonic decreasing deque that stores indices (not values). The invariant: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Before adding index i:
- Remove expired indices from the front: if
deque[0] <= i - k, the index has left the window. - Remove smaller indices from the back: while
nums[deque[-1]] <= nums[i], those indices can never be the max of any future window (they are to the left and smaller), so discard them.
After these operations, push i to the back. The front always gives the maximum of the current window.
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # stores indices; values are decreasing
result = []
for i, n in enumerate(nums):
# 1. Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# 2. Remove indices with smaller values from the back
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
# 3. Record max when first full window is complete
if i >= k - 1:
result.append(nums[dq[0]]) # front = max of current window
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3)) # [3, 3, 5, 5, 6, 7]Tracing the Deque Step by Step
Let us trace [1, 3, -1, -3, 5, 3, 6, 7] with k=3:
- i=0 (1): dq=[0]
- i=1 (3): pop 0 (1<3), dq=[1]
- i=2 (-1): -1<3 so keep, dq=[1,2]. Window [1,3,-1], max=nums[1]=3
- i=3 (-3): -3<-1, dq=[1,2,3]. Check front: 1 > 3-3=0, OK. Window max=3
- i=4 (5): pop 3,2,1 (all smaller), dq=[4]. Front 4 > 4-3=1, OK. Max=5
- i=5 (3): 3<5, dq=[4,5]. Front 4 > 5-3=2, OK. Max=5
- i=6 (6): pop 5,4 (both smaller), dq=[6]. Max=6
- i=7 (7): pop 6, dq=[7]. Max=7
from collections import deque
def sliding_window_max_trace(nums, k):
dq = deque()
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
print(f' Remove expired index {dq[0]} from front')
dq.popleft()
while dq and nums[dq[-1]] <= n:
print(f' Remove smaller index {dq[-1]} (val={nums[dq[-1]]}) from back')
dq.pop()
dq.append(i)
print(f'i={i} n={n}: dq={list(dq)} vals={[nums[j] for j in dq]}')
if i >= k - 1:
win_max = nums[dq[0]]
result.append(win_max)
print(f' Window {nums[max(0,i-k+1):i+1]} -> max={win_max}')
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
result = sliding_window_max_trace(nums, 3)
print('Result:', result)Why Each Element Is Pushed and Popped At Most Once
The O(n) guarantee comes from the same amortised argument as the monotonic stack: each index is appended to the deque exactly once and removed (either from the front when expired or from the back when superseded) at most once. Total deque operations across the entire loop are at most 2n.
The inner while loops do not increase overall complexity — any popping done in those loops is 'paid for' by the earlier push. This is the same reasoning as the monotonic stack, but extended to a deque that allows removal from both ends.
from collections import deque
def sliding_window_max_instrumented(nums, k):
dq = deque()
result = []
front_pops = back_pops = pushes = 0
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft(); front_pops += 1
while dq and nums[dq[-1]] <= n:
dq.pop(); back_pops += 1
dq.append(i); pushes += 1
if i >= k - 1:
result.append(nums[dq[0]])
print(f'n={len(nums)}: pushes={pushes}, front_pops={front_pops}, back_pops={back_pops}')
print(f'Total deque ops = {pushes + front_pops + back_pops} <= 3n = {3*len(nums)}')
return result
import random; random.seed(0)
nums = [random.randint(-100, 100) for _ in range(20)]
sliding_window_max_instrumented(nums, 5)Sliding Window Minimum
The sliding window minimum is the symmetric counterpart: maintain a monotonic increasing deque (pop from back when the new element is smaller than the back). The front always holds the minimum of the current window. Every other step is identical to the maximum version — just flip the comparison direction.
Problems that ask for sliding-window minimum often appear as sub-problems inside larger algorithms. For example, minimum cost to move goods along a path with k intermediate stops can require sliding-window minimum over DP arrays.
from collections import deque
def sliding_window_min(nums, k):
dq = deque() # increasing monotonic deque
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft() # expired
while dq and nums[dq[-1]] >= n:
dq.pop() # pop larger values from back
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]]) # front = min
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print('Max k=3:', sliding_window_min.__name__, '->', end=' ')
print(sliding_window_min(nums, 3)) # [-1, -3, -3, -3, 3, 3]
from collections import deque
def sliding_window_max(nums, k):
dq = deque(); result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i-k: dq.popleft()
while dq and nums[dq[-1]] <= n: dq.pop()
dq.append(i)
if i >= k-1: result.append(nums[dq[0]])
return result
print('Max k=3:', sliding_window_max(nums, 3)) # [3,3,5,5,6,7]Jump Game VI: DP with Monotonic Deque
Jump Game VI (LeetCode 1696) is a classic example where DP and monotonic deque combine. Given an array and a max jump size k, starting at index 0, each step you jump 1 to k steps forward adding the target cell's score. Maximise the total score. The DP recurrence is dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). A sliding window maximum over the DP array gives O(n) total.
This pattern — DP recurrence where each cell depends on the maximum of a fixed-size window of previous cells — appears frequently and always calls for a monotonic deque.
from collections import deque
def max_result(nums, k):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dq = deque([0]) # indices of max dp values in current window
for i in range(1, n):
# Remove expired indices
while dq and dq[0] < i - k:
dq.popleft()
# dp[i] = nums[i] + max dp in window [i-k, i-1]
dp[i] = nums[i] + dp[dq[0]]
# Maintain decreasing deque on dp values
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return dp[n - 1]
print(max_result([1,-1,-2,4,-7,3], 2)) # 7: path 1->4->3
print(max_result([10,-5,-2,4,0,3], 3)) # 17: path 10->4->3
print(max_result([1,-5,-20,4,-1,3,-6,-3], 2)) # 0Sliding Window Maximum: Segment Tree Alternative
For problems where the window size varies (not fixed k), the monotonic deque does not directly apply. Instead, use a sparse table for static range-max queries in O(1) per query after O(n log n) preprocessing, or a segment tree for dynamic updates with O(log n) per query. However, for fixed-k sliding windows, the deque is unbeatable at O(n).
In interviews, always prefer the O(n) monotonic deque over the O(n log n) segment tree when the window size is constant. Mention the trade-off: the deque cannot handle arbitrary window sizes or updates, while segment trees can.
# Sparse table for static RMQ (range maximum query)
import math
def build_sparse_table(arr):
n = len(arr)
LOG = int(math.log2(n)) + 1 if n else 1
table = [[0]*n for _ in range(LOG)]
table[0] = arr[:]
j = 1
while (1 << j) <= n:
for i in range(n - (1 << j) + 1):
table[j][i] = max(table[j-1][i], table[j-1][i + (1 << (j-1))])
j += 1
return table
def query(table, l, r):
k = int(math.log2(r - l + 1))
return max(table[k][l], table[k][r - (1 << k) + 1])
arr = [1, 3, -1, -3, 5, 3, 6, 7]
table = build_sparse_table(arr)
k = 3
result = [query(table, i, i + k - 1) for i in range(len(arr) - k + 1)]
print('Sparse table result:', result) # [3, 3, 5, 5, 6, 7]Longest Subarray of Ones After Deleting One Element
LeetCode 1493: given a binary array, find the length of the longest subarray of 1s after deleting exactly one element (which can be a 0 or a 1). This is a sliding-window problem. Maintain a window with at most one 0. When the window has more than one 0, shrink from the left.
This uses the variable-size sliding window pattern — not a deque. However, pairing it with the maximum-window technique: after finding all valid windows, the maximum length is the answer. The 'delete one element' means we allow exactly one 0 in our window of 1s.
def longest_subarray(nums):
left = 0
zeros = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
while zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
# Window [left, right] has at most 1 zero
# After deleting one element, length = right - left (not +1, since we delete one)
max_len = max(max_len, right - left)
return max_len
print(longest_subarray([1,1,0,1])) # 3: delete the 0
print(longest_subarray([0,1,1,1,0,1,1,0,1])) # 5
print(longest_subarray([1,1,1])) # 2: must delete one 1Deque vs Queue vs Stack Comparison
Understanding when to use each container is key for interviews:
- Stack (list): LIFO, single end access. Use for DFS, expression parsing, monotonic stack problems.
- Queue (deque with appendleft/popleft): FIFO, single-end push, other-end pop. Use for BFS, task scheduling.
- Deque: both ends accessible in O(1). Use for sliding-window with expiry (remove front) and monotonic invariant (remove back). The sliding-window maximum is the canonical deque problem.
Python's collections.deque is the tool for all three. Use append/pop for stack behaviour and append/popleft or appendleft/pop for queue/deque behaviour.
from collections import deque
# deque as stack
stack = deque()
stack.append(1); stack.append(2); stack.append(3)
print('Stack pop:', stack.pop()) # 3 (LIFO)
# deque as queue
queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print('Queue pop:', queue.popleft()) # 1 (FIFO)
# deque as sliding window with front expiry + back monotonic
dq = deque()
nums = [3, 1, 4, 1, 5, 9, 2, 6]
k = 3
for i, n in enumerate(nums):
while dq and dq[0] <= i - k: dq.popleft() # expire front
while dq and nums[dq[-1]] <= n: dq.pop() # maintain back
dq.append(i)
if i >= k - 1:
print(f'Window {nums[max(0,i-k+1):i+1]}: max={nums[dq[0]]}')Shortest Subarray with Sum At Least K: Deque + Prefix Sums
Shortest Subarray with Sum at Least K (LeetCode 862) is an advanced problem combining prefix sums with a monotonic deque. Build prefix sums, then use a deque to find, for each right endpoint, the leftmost prefix sum that satisfies prefix[right] - prefix[left] >= k. The deque maintains increasing prefix sums (pop from back to keep increasing), and pops from front to collect valid answers.
This is one of the hardest sliding-window problems because it involves negative numbers (ruling out simple two-pointer) and requires the deque to serve both as a monotonic structure and as an expiry mechanism.
from collections import deque
def shortest_subarray(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
dq = deque() # monotonic increasing deque of indices into prefix
result = float('inf')
for right in range(n + 1):
# Pop from front: valid subarrays ending at `right`
while dq and prefix[right] - prefix[dq[0]] >= k:
result = min(result, right - dq.popleft())
# Pop from back: maintain increasing deque
while dq and prefix[dq[-1]] >= prefix[right]:
dq.pop()
dq.append(right)
return result if result != float('inf') else -1
print(shortest_subarray([1], 1)) # 1
print(shortest_subarray([1, 2], 4)) # -1
print(shortest_subarray([2, -1, 2], 3)) # 3
print(shortest_subarray([84,-37,32,40,95], 167)) # 3Interview Strategy for Deque Problems
Identify a monotonic deque problem by these signals: (1) you need the maximum or minimum of a sliding window of fixed size, (2) you need DP recurrence dp[i] = f(nums[i], max(dp[i-k..i-1])), or (3) you need the nearest valid index satisfying a monotonic condition.
In interviews, code the deque solution cleanly: import deque, maintain the two invariants (front expiry, back monotonicity), and return results starting from index k-1. Always mention the O(n) time complexity and O(k) space for the deque (at most k indices stored at once), and compare to the O(nk) brute force to show the improvement.
from collections import deque
# Clean, interview-ready template
def sliding_window_max_template(nums, k):
if not nums or k == 0:
return []
dq = deque() # monotonic decreasing, stores indices
result = []
for i in range(len(nums)):
# Invariant 1: remove expired indices (outside window)
while dq and dq[0] < i - k + 1:
dq.popleft()
# Invariant 2: remove indices with smaller values (useless)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Record result once first full window is established
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Complexity: O(n) time, O(k) space
print(sliding_window_max_template([1,3,-1,-3,5,3,6,7], 3))
print(sliding_window_max_template([1], 1))
print(sliding_window_max_template([], 3))Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: a monotonic decreasing deque maintains the window maximum at its front while discarding elements from the back that are smaller than new arrivals, expired indices are removed from the front when they fall outside the window boundary, and each index is pushed and popped at most once giving O(n) overall with O(k) deque space. Next up we solve trapping rain water using both the monotonic stack and the two-pointer approach.
Frequently asked questions
Is the “Sliding Window Maximum with Monotonic Deque” lesson free?
Yes — the full text of “Sliding Window Maximum with Monotonic Deque” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Sliding Window Maximum with Monotonic Deque”?
Maintain a decreasing deque of indices to answer maximum-in-window queries in O(1) per element, solving the sliding-window-maximum problem in O(n). You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Sliding Window Maximum with Monotonic Deque” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Monotonic Stack: Increasing vs Decreasing
- Largest Rectangle in Histogram
- Sliding Window Maximum with Monotonic Deque
- Trapping Rain Water: Stack and Two-Pointer