Intermediate · Module 7 · Lesson 4
Monotonic deque window
Maintain range minima or maxima in linear time.
15–25 min readLesson 40 of 123
Lesson 40 of 123
1d streakTheory lesson · Step-by-step
Understand Monotonic deque window
Maintain range minima or maxima in linear time.
Worked approach
Trace the reasoning step by step
- 1Remove the outgoing index from the front.
- 2Remove dominated values from the back.
- 3Append the incoming index.
- 4Read the extreme from the front.
Concrete example
Find maxima of size-3 windows in [1,3,-1,-3,5,3,6,7].
- 1Remove smaller tails before adding each value.
- 2Remove the front when it leaves the window.
Window maxima are [3,3,5,5,6,7].
What must remain true (Loop Invariant)
Deque indexes stay inside the window and their values remain monotonic.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Window traversal
Usually O(n)
O(1) to O(k)
Each boundary moves forward; state size depends on the condition.When to use it
- Contiguous subarrays or substrings with incrementally maintainable state.
- Longest, shortest, count, sum, or frequency constraints.
- Streaming range calculations.
Common mistakes
- Using a variable window when feasibility is not monotonic under shrinking.
- Adding an incoming item but forgetting to remove the outgoing one.
- Updating the answer before the window is valid.
Practice prompts
- Reproduce the worked Monotonic deque window example without looking at the trace.
- Change one input condition and explain whether the Monotonic deque window invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.