Sliding Window Maximum with Deque
Keep window extremes in O(n).
Sliding Window Maximum with Deque is a free Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy course, upgrade to CoddyKit PRO.
What will I learn in “Sliding Window Maximum with Deque”?
Keep window extremes in O(n). You practise Competitive Programming Academy 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 Competitive Programming Academy?
No prior experience is required. Competitive Programming Academy 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 Competitive Programming Academy lesson?
Yes. Every Competitive Programming Academy 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