Course contentsShow
← Computer Science
Lesson 957 of 2,87222. Dynamic ProgrammingFree lesson

Monotonic Queue Optimization

Use deques to maintain range minimums/maximums in O(1) amortized time for sliding window DP.

Monotonic Queue Optimization

You'll learn how to use a deque (double-ended queue) to maintain range minimums or maximums in constant amortized time, supercharging sliding-window DP problems.

The Core Idea

Imagine you're tracking the minimum value in a sliding window that moves across an array. The naive approach checks every element in the window each time—costly! Monotonic Queue Optimization keeps a deque of candidates that could be the minimum (or maximum), arranged in increasing (or decreasing) order.

The trick: when a new element arrives, you remove useless elements from the back—any element smaller than the newcomer will never be the minimum again because the newcomer is both larger and will stay valid longer. Then you remove expired elements from the front that have slid out of the window.

Why It Works

Think of it like a line of job applicants sorted by skill. If someone arrives who's more skilled and younger than people ahead of them, those older folks can't possibly get hired—so they leave. When you need the best candidate, you just look at the front of the line.

Each element enters the deque once and leaves once, giving O(1) amortized time per operation instead of O(k) for a window of size k.

In DP Context

Many DP problems require finding min(dp[i-k], dp[i-k+1], ..., dp[i-1]) to compute dp[i]. Instead of scanning k elements every time, maintain a monotonic deque of indices (sorted by their dp values). This transforms O(nk) solutions into O(n).

Key Takeaway: Monotonic queues maintain range extrema in O(1) amortized time by discarding elements that can never be optimal, making sliding-window DP problems dramatically faster.