Sliding Window Maximum with Deque
Keep window extremes in O(n).
Sliding Window Maximum with Deque is a free Coding Interview Prep lesson on CoddyKit — lesson 4 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 Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Sliding Window Max
Given an array and a window size k, you want the maximum of every window as it slides right. Doing it naively is O(n times k).
A Faster Promise
With a monotonic deque you can answer every window in total O(n) time, scanning the array just once.
Store Indices Again
Keep indices in the deque, not values. Indices let you check whether the front has slid out of the current window.
from collections import deque
dq = deque()
res = []Keep It Decreasing
The deque stays decreasing by value from front to back, so the front index always points to the window maximum.
Drop Smaller Tails
Before adding index i, pop from the back while those values are smaller, since they can never be a future maximum.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Append the New Index
After clearing weaker tails, append the current index. The deque order stays correct for the next steps.
dq.append(i)Evict the Stale Front
If the front index falls outside the window, popleft it. A window of size k starts at index i minus k plus one.
if dq[0] <= i - k:
dq.popleft()Record Each Maximum
Once the first full window forms at index k minus one, the deque front holds the answer for every position onward.
if i >= k - 1:
res.append(nums[dq[0]])Mind the Eviction Order
Evict the stale front before reading the answer. Otherwise you might report a maximum that already left the window.
Why Linear Time Holds
Each index is added and removed at most once, so the deque work is amortized O(1) per step and O(n) overall.
Min Window, Same Idea
For a sliding window minimum, keep the deque increasing instead. Just flip the comparison when trimming the back.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Quick Check
In sliding window maximum, what does the front of the monotonic deque hold?
Recap: Deque Wins the Window
You kept a decreasing deque of indices: trim small tails, evict the stale front, read the front for each window max in O(n). 🏆
Frequently asked questions
Is the “Sliding Window Maximum with Deque” lesson free?
Yes — the full text of “Sliding Window Maximum with Deque” is free to read here on the web, and the Coding 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 Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Sliding Window Maximum with Deque”?
Keep window extremes in O(n). You practise Coding 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 Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 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 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 Coding Interview Prep lesson?
Yes. Every Coding 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
- Stacks for Matching Brackets
- Monotonic Stack: Next Greater Element
- Queues and collections.deque
- Sliding Window Maximum with Deque