Monotonic Queue

A deque-shaped trick for sliding-window min/max queries: keep only the elements that can still matter, and every step becomes amortized $O(1)$.

Difficulty: Intermediate | Prerequisites: Stack, Queue, and Deque, Monotonic Stack | CF Rating Range: 1500–2200

Intuition

You have the array [5, 3, 7, 1, 2, 6, 4] and you need the maximum in every contiguous window of size $k=3$.

The obvious solution is to move the window one step at a time, scan all $k$ elements, and take the max.

Window 1:  |5  3  7| 1  2  6  4   scan 5, 3, 7  -->  max = 7
Window 2:   5 |3  7  1| 2  6  4   scan 3, 7, 1  -->  max = 7
Window 3:   5  3 |7  1  2| 6  4   scan 7, 1, 2  -->  max = 7
Window 4:   5  3  7 |1  2  6| 4   scan 1, 2, 6  -->  max = 6
Window 5:   5  3  7  1 |2  6  4|  scan 2, 6, 4  -->  max = 6

Five windows $\times$ 3 elements = 15 element reads. Look at 7 at index 2: you read it in window 1, again in window 2, again in window 3. You already knew it was the champion, but the loop kept re-discovering it. Scale this up to $n={10}^6$ and $k=500$, and the naive approach performs roughly $5\times {10}^8$ reads—a guaranteed TLE on a 1-second limit. Most of this work buys nothing.

Picture a running scoreboard at a sports bar. When a new high score arrives, the bartender wipes every lower score off the board—those players can never reclaim "current leader." The board stays in decreasing order, top to bottom, and the top entry is the answer.

Where the analogy breaks: on the scoreboard, the top score stays forever. In a sliding window, even the leader eventually expires when the window moves past its position. So there are two things to handle—discard losers from the back, expire aged leaders from the front. The data structure that supports both is a deque, and the discipline that keeps its values sorted is the monotonic queue.

Visual Walkthrough

Same array: [5, 3, 7, 1, 2, 6, 4], $k=3$. The deque stores indices, not values, so we can tell both the value and whether it has expired. We keep the deque non-increasing from front to back, which makes the front the current maximum.

Step 1: i=0, val=5
  Deque empty. Push index 0.

  array:  | 5 | 3 | 7 | 1 | 2 | 6 | 4 |
            ^
  deque:  front +---+ back
                | 5 |
                +---+

  Window not full yet -- no answer.


Step 2: i=1, val=3
  Back val 5 > 3, no pop. Push index 1.

  array:  | 5 | 3 | 7 | 1 | 2 | 6 | 4 |
            ^   ^
  deque:  front +---+---+ back
                | 5 | 3 |
                +---+---+

  Window not full yet -- no answer.


Step 3: i=2, val=7
  Back val 3 <= 7  -->  pop index 1
  Back val 5 <= 7  -->  pop index 0
  Deque empty. Push index 2.

  array:  | 5 | 3 | 7 | 1 | 2 | 6 | 4 |
            <--------->
                  ^
  deque:  front +---+ back
                | 7 |
                +---+
                  ^--- front = window max

  * Answer = 7 *


Step 4: i=3, val=1
  Back val 7 > 1, no pop. Push index 3.

  array:  | 5 | 3 | 7 | 1 | 2 | 6 | 4 |
                <--------->
  deque:  front +---+---+ back
                | 7 | 1 |
                +---+---+

  Front index 2 -- inside window [1,3]? 2 > i-k = 0, yes.
  * Answer = 7 *


Step 5: i=4, val=2
  Back val 1 <= 2  -->  pop index 3
  Back val 7 > 2, stop. Push index 4.

  array:  | 5 | 3 | 7 | 1 | 2 | 6 | 4 |
                    <--------->
  deque:  front +---+---+ back
                | 7 | 2 |
                +---+---+

  Front index 2 -- inside window [2,4]? 2 > i-k = 1, yes.
  * Answer = 7 *


Step 6: i=5, val=6    *** front expiry happens here ***
  Back val 2 <= 6  -->  pop index 4
  Back val 7 > 6, stop. Push index 5.

  deque after push:  front +---+---+ back
                           | 7 | 6 |
                           +---+---+

  Front index 2 -- inside window [3,5]? 2 <= i-k = 2, NO!
  Pop front. Index 2 has expired.

  deque after expiry: front +---+ back
                            | 6 |
                            +---+

  array:  | 5 | 3 | 7 | 1 | 2 | 6 | 4 |
                        <--------->
  * Answer = 6 *


Step 7: i=6, val=4
  Back val 6 > 4, no pop. Push index 6.

  array:  | 5 | 3 | 7 | 1 | 2 | 6 | 4 |
                            <--------->
  deque:  front +---+---+ back
                | 6 | 4 |
                +---+---+

  Front index 5 -- inside window [4,6]? 5 > i-k = 3, yes.
  * Answer = 6 *

Answers: 7, 7, 7, 6, 6. Correct.

7 pushes + 4 back-pops + 1 front-pop = 12 deque operations. Every element entered the deque exactly once and left it at most once. The gap over brute force is small here because $n$ is small—but it explodes with scale. For $n={10}^6$ and $k=500$, brute force does $\sim 5\times {10}^8$ work while the monotonic queue does at most $2\times {10}^6$.

The Invariant

+-------------------------------------------------------------------+
| The deque values are always in non-increasing order (front to     |
| back). The front is the current window maximum. Every index       |
| stored in the deque lies within the current window bounds.        |
+-------------------------------------------------------------------+

Why it is maintained—two rules:

1. Back-pop rule: Before pushing a new element, pop every back element whose value $\le$ the new value. This preserves the decreasing order. (Step 3 above: values 3 and 5 disappear because the incoming 7 dominates them.)

2. Front-pop rule: After pushing, check whether the front index has left the window. If so, pop it. This keeps the deque aligned with the current window bounds. (Step 6 above: index 2 expired when the window advanced to positions $[3,5]$.)

Step 6 is the failure mode to remember. Index 2 (value 7) is no longer inside the window $[3,5]$. Without the expiry check, we would incorrectly report 7 as the maximum of [1, 2, 6]. The front-pop rule removes that stale leader before it can corrupt the answer.

Amortized $O(1)$ per element: Each of the $n$ elements is pushed exactly once and popped at most once, from either end. That gives at most $2n$ deque operations total—$n$ pushes plus at most $n$ pops—so the whole scan stays $O(n)$.

The Deque Stores Candidates, Not the Window

This is the most important mental shift. The deque never holds all $k$ elements in the current window—it holds only the subset that could still become the answer for some future window. Most elements disappear early because a newer, better value arrives.

Array:     8  3  5  1  4  2         (k = 3, window max)
Index:     0  1  2  3  4  5

  i | val | Action              | Deque (front->back)  | Window  | Answer
 ---+-----+---------------------+---------------------+---------+-------
  0 |  8  | push 0              | [0:8]               |   --     |   --
  1 |  3  | push 1              | [0:8  1:3]          |   --     |   --
  2 |  5  | pop 1, push 2       | [0:8  2:5]          | [0,2]   |   8
  3 |  1  | push 3, EXPIRE 0    | [2:5  3:1]          | [1,3]   |   5
  4 |  4  | pop 3, push 4       | [2:5  4:4]          | [2,4]   |   5
  5 |  2  | push 5, EXPIRE 2    | [4:4  5:2]          | [3,5]   |   4

  Window has 3 elements, but the deque never holds more than 2.
  Dominated elements are removed before they ever matter again.

The Two Doors

Every element enters through one door and exits through exactly one of two:

• Back door (dominated): When a new element $a[i]$ arrives, every element at the back that is $\le a[i]$ is strictly worse and older—it can never win again. Pop it from the back.
• Front door (expired): Even the current champion eventually ages out of the window. Check the front index before reading the answer and pop if stale.

                        +--------------------------+
     expired indices    |  Deque  (non-increasing)  |    dominated
     leave this way <-- |  front .....-> back       | --> elements
        (front pop)     |  [best]      [newest]     |    popped here
                        +--------------------------+     (back pop)

The front-pop is lazy—you do not scan the deque eagerly for expired indices. You check only the front, because only the front can be stale. That is what keeps the constant factor tiny.

The textbook example is fixed-size $k$, but the technique generalizes to variable-size windows controlled by two pointers. For "longest subarray where $max-min\le d$," you maintain two deques—one for maxima and one for minima—and advance the left pointer whenever the constraint breaks. The expiry condition changes from front <= i - k to front < left.

Every element has exactly one life in the deque: it enters through the back and exits through exactly one of the two doors—back if a newer, bigger value dominates it, front if it ages out of the window. At most $2n$ operations total, regardless of $k$.

  Element lifecycle:

       PUSH (back)                      POP (back or front)
          |                                    |
          v                                    v
    +-----------+    lives in deque     +-------------+
    | Enter once | ------------------- | Leave once   |
    +-----------+   (as a candidate)    +-------------+

    n pushes + at most n pops = 2n operations.
    Amortized cost per element: O(1).

When to Reach for This

If a problem keeps asking for the best value inside a window that moves monotonically, reach for a monotonic queue:

1. "Maximum (or minimum) in every subarray of size $k$." The textbook use case.
2. "DP where each state depends on the min/max over the previous $k$ states"—the monotonic queue optimizes the transition from $O(nk)$ to $O(n)$.
3. "Longest subarray where max $-$ min $\le d$." Use two monotonic queues (one for max, one for min) together with two pointers.
4. "Sliding window" combined with "$n\le {10}^6$"—a multiset gives $O(n\log n)$ but the monotonic queue gives $O(n)$ and avoids TLE.
5. "Minimum cost to traverse with bounded jump size"—often a DP with range-min transition that a monotonic queue handles.

Counter-examples—looks like monotonic queue, but is not:

1. "Sliding window sum or average." You just need a running total, adding the new element and subtracting the expired one. No monotonic structure required—use prefix sums.
2. "Find the next greater element for each position." Similar monotonic flavor, but there is no sliding window and no element expiry. You want a Monotonic Stack instead.
3. "Range min/max with arbitrary query endpoints." The query endpoints do not advance monotonically, so the deque trick does not apply. Use a Sparse Table or Segment Tree.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
std::deque<T>	<deque>	Double-ended queue with $O(1)$ push/pop at both ends	--
dq.push_back(x)	<deque>	Insert at back	$O(1)$ amortized
dq.pop_back()	<deque>	Remove from back	$O(1)$
dq.push_front(x)	<deque>	Insert at front	$O(1)$ amortized
dq.pop_front()	<deque>	Remove from front	$O(1)$
dq.front()	<deque>	Access front element	$O(1)$
dq.back()	<deque>	Access back element	$O(1)$
dq.empty()	<deque>	Check if empty	$O(1)$

Note: In contest code, you only need push_back, pop_back, pop_front, front, back, and empty. You never use push_front for a monotonic queue.

---

Implementation

Sliding Window Maximum — Minimal Template

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    deque<int> dq; // stores indices
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) printf("%d ", a[dq.front()]);
    }
    return 0;
}

Sliding Window Maximum — Annotated

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    // Deque stores indices, not values. This lets us check expiry.
    deque<int> dq;

    for (int i = 0; i < n; i++) {
        // INVARIANT: deque values are non-increasing (front = max).
        // Any back element <= a[i] can never be the max for any future
        // window that includes i, because a[i] is both newer and bigger.
        while (!dq.empty() && a[dq.back()] <= a[i])
            dq.pop_back();

        dq.push_back(i);

        // Expire: if the front index is outside the window [i-k+1, i],
        // it is no longer part of the current window. Remove it.
        if (dq.front() <= i - k)
            dq.pop_front();

        // Output once the first full window is formed (i >= k-1).
        if (i >= k - 1)
            printf("%d ", a[dq.front()]);
    }
}

Sliding Window Minimum

One character changes. For the minimum, maintain a non-decreasing deque—pop the back while it is $\ge$ the new value.

while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();

Sliding Window Min and Max Together (CSES-style)

Two deques in the same loop, one for the max and one for the min.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    vector<int> win_max(n - k + 1), win_min(n - k + 1);
    deque<int> mx, mn;  // mx: non-increasing (max), mn: non-decreasing (min)

    for (int i = 0; i < n; i++) {
        while (!mx.empty() && a[mx.back()] <= a[i]) mx.pop_back();
        while (!mn.empty() && a[mn.back()] >= a[i]) mn.pop_back();
        mx.push_back(i);
        mn.push_back(i);
        if (mx.front() <= i - k) mx.pop_front();
        if (mn.front() <= i - k) mn.pop_front();
        if (i >= k - 1) {
            win_max[i - k + 1] = a[mx.front()];
            win_min[i - k + 1] = a[mn.front()];
        }
    }

    for (int i = 0; i <= n - k; i++) printf("%d%c", win_max[i], " \n"[i == n - k]);
    for (int i = 0; i <= n - k; i++) printf("%d%c", win_min[i], " \n"[i == n - k]);
}

Example: Input 7 3 / 5 3 7 1 2 6 4 → Max: 7 7 7 6 6 / Min: 3 1 1 1 2.

DP Optimization with Bounded Transitions

When a DP recurrence takes its minimum over a moving range of previous states, the monotonic queue replaces the inner loop. See Pattern: DP Optimization below for the full worked example.

Operations Reference

Operation	Time	Space
Build over array of $n$ elements	$O(n)$	$O(k)$
Query current window max/min	$O(1)$	--
Slide window by one position	$O(1)$ amortized	--
Total for all $n$ windows	$O(n)$	$O(k)$

Each element enters and leaves the deque at most once, so the total work across all slides is $O(n)$, not $O(nk)$.

Comparison: Sliding Window Techniques

Feature	Monotonic Queue	Segment Tree	Sparse Table	Multiset
Build time	$O(n)$	$O(n)$	$O(n\log n)$	$O(n\log n)$
Per-window query	$O(1)$ amortized	$O(\log n)$	$O(1)$	$O(\log n)$
Total for $n$ windows	$O(n)$	$O(n\log n)$	$O(n)$	$O(n\log n)$
Supports updates	No	Yes	No	Yes
Arbitrary query range	No	Yes	Yes	Yes
Code complexity	~4 lines	~40 lines	~20 lines	~5 lines
Best for	Sliding window	Dynamic + arbitrary	Static + arbitrary	Small $n$

Rule of thumb: If the window slides one position at a time and you only need min/max, use the monotonic queue—it beats everything in speed and simplicity. Reach for a Segment Tree when you need updates or arbitrary ranges, and a Sparse Table for static arbitrary-range queries.

---

Problem Patterns & Tricks

Direct Sliding Window Min/Max

The classic. Given array and window size $k$, output the max (or min) in each window.

// Core loop -- just the 4 lines above.
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if (dq.front() <= i - k) dq.pop_front();
if (i >= k - 1) ans.push_back(a[dq.front()]);

Problems: CF 1611F, CF 940E

DP Optimization with Bounded Transition Range

When a DP recurrence looks like $dp[i]=\underset{j\in [i-k,i-1]}{min}dp[j]+cost(i)$, use a monotonic queue over the DP values to compute the $min$ in $O(1)$ per state.

deque<int> dq;
for (int i = 0; i < n; i++) {
    while (!dq.empty() && dq.front() < i - k) dq.pop_front();
    if (!dq.empty()) dp[i] = dp[dq.front()] + cost[i];
    while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
    dq.push_back(i);
}

Problems: CF 487B, CF 372C

Worked Example: Minimum-Cost Bounded Jump

Problem: You stand at position 0 of an array cost[0..n-1]. From position $i$ you can jump to any position in $[i+1,min(i+k,n-1)]$. Reaching position $i$ costs cost[i]. Find the minimum total cost to reach position $n-1$.

Recurrence: $dp[i]=min(dp[j]\text{ for }j\in [max(0,i-k),i-1])+cost[i]$, with base case $dp[0]=cost[0]$.

Without a monotonic queue, the inner $min$ takes $O(k)$ per state—$O(nk)$ total. With a min-queue on $dp$ values, it's $O(1)$ amortized per state—$O(n)$ total.

Trace: cost = [3, 2, 5, 1, 6, 4], $k=3$.

cost = [3, 2, 5, 1, 6, 4], k = 3

i=0: dp[0] = cost[0] = 3  (base case)
     Push 0.  Deque: [0:3]

i=1: Expire: 0 < 1-3 = -2? No.
     dp[1] = dp[0] + cost[1] = 3 + 2 = 5
     Back-pop: dp[0]=3 < 5, stop.  Push 1.  Deque: [0:3, 1:5]

i=2: Expire: 0 < 2-3 = -1? No.
     dp[2] = dp[0] + cost[2] = 3 + 5 = 8
     Back-pop: dp[1]=5 < 8, stop.  Push 2.  Deque: [0:3, 1:5, 2:8]

i=3: Expire: 0 < 3-3 = 0? No.
     dp[3] = dp[0] + cost[3] = 3 + 1 = 4
     Back-pop: dp[2]=8 >= 4, pop.  dp[1]=5 >= 4, pop.  dp[0]=3 < 4, stop.
     Push 3.  Deque: [0:3, 3:4]

i=4: Expire: 0 < 4-3 = 1? Yes, pop 0.  Deque: [3:4]
     dp[4] = dp[3] + cost[4] = 4 + 6 = 10
     Back-pop: dp[3]=4 < 10, stop.  Push 4.  Deque: [3:4, 4:10]

i=5: Expire: 3 < 5-3 = 2? No.
     dp[5] = dp[3] + cost[5] = 4 + 4 = 8
     Back-pop: dp[4]=10 >= 8, pop.  dp[3]=4 < 8, stop.
     Push 5.  Deque: [3:4, 5:8]

Answer: dp[5] = 8   (path: 0 -> 3 -> 5, costs 3 + 1 + 4 = 8)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> cost(n);
    for (int i = 0; i < n; i++) scanf("%d", &cost[i]);

    vector<int> dp(n, INT_MAX);
    dp[0] = cost[0];

    deque<int> dq;
    dq.push_back(0);

    for (int i = 1; i < n; i++) {
        while (!dq.empty() && dq.front() < i - k) dq.pop_front();
        dp[i] = dp[dq.front()] + cost[i];
        while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
        dq.push_back(i);
    }

    printf("%d\n", dp[n - 1]);
}

Order of operations—getting this wrong is the #1 DP + monotonic queue bug:

1. Expire front—remove indices outside the valid range $[i-k,i-1]$
2. Compute dp[i]—read dp[dq.front()], which is the range minimum
3. Back-pop—remove dominated values (those $\ge$ dp[i])
4. Push i—add the newly computed dp[i] to the deque

If you push before computing dp[i], the deque contains an uninitialized or self-referencing value and every transition that follows is corrupt.

Longest Subarray with Bounded Max-Min Difference

Count or find the longest subarray where $max-min\le d$. Two monotonic queues—one for max, one for min—combined with two pointers.

deque<int> mx, mn;
int l = 0;
for (int r = 0; r < n; r++) {
    while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
    while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
    mx.push_back(r); mn.push_back(r);
    while (a[mx.front()] - a[mn.front()] > d) {
        l++;
        if (mx.front() < l) mx.pop_front();
        if (mn.front() < l) mn.pop_front();
    }
    ans += r - l + 1; // or track max length
}

The expiry condition changes from front <= i - k (fixed window) to front < l (variable window driven by the left pointer).

2D Sliding Window

For minimum (or maximum) in every $k\times k$ subgrid: apply the 1D monotonic queue to each row, then apply it to each column of the intermediate result. Total $O(nm)$.

Monotonic Queue inside Binary Search

Binary search on the answer (e.g., "is there a subarray of length $\ge k$ with max $-$ min $\le$ mid?"), and check feasibility with a monotonic queue in $O(n)$.

Problems: CF 1918D

Sum/Cost Optimization with Sliding Window

Minimize cost over windows. E.g., "choose exactly $k$ consecutive elements minimizing some function." The monotonic queue replaces an inner loop.

Problems: CF 1077F2

---

Contest Cheat Sheet

Sliding window max:  array = [5, 3, 7, 1]   k = 3

MONOTONIC DEQUE                         MAX-HEAP (priority_queue)
─────────────────                       ──────────────────────────

After processing 5, 3, 7:              After processing 5, 3, 7:

  front → | 7 | ← back                     ┌───┐
           +---+                            | 7 |   ← top
  Size: 1  (5, 3 already popped —           ├───┤
  they can never be max)                    | 5 |   ← still here!
                                            ├───┤
                                            | 3 |   ← still here!
                                            └───┘
                                            Size: 3  (dead weight)

Total across n elements:
  Deque:  n pushes + n pops   = O(n)
  Heap:   n pushes × O(log n) = O(n log n)

For $n={10}^6$, that's $\sim 20\times$ more work.

When Not to Use

• Arbitrary range queries (not a sliding window). Use Sparse Table or Segment Tree.
• Need updates. The monotonic queue is a one-pass structure.
• Sliding window sum / average. Just maintain a running sum: sum += a[i]; if (i >= k) sum -= a[i-k];. Prefix sums also work. Monotonic structures are specifically for extrema.
• Median of the window. Use two heaps or a policy-based tree.
• Non-contiguous windows. The deque assumes the window slides one step at a time.
• Next greater element. No window, no expiry—use a Monotonic Stack.

Why Not priority_queue or a Segment Tree?

priority_queue: A max-heap does give you the current maximum in $O(1)$, but pushing is $O(\log n)$ and expired elements linger because you can't efficiently remove from the middle. You end up doing lazy deletion, which keeps dead weight around and makes each operation $O(\log n)$ instead of amortized $O(1)$.

  Deque vs. Heap — after processing [5, 3, 7] with k = 3:

  MONOTONIC DEQUE                    MAX-HEAP (priority_queue)
  ─────────────────                  ──────────────────────────

  front -> | 7 | <- back                  +---+
           +---+                          | 7 |   <- top
  Size: 1  (5, 3 already popped)          +---+
                                          | 5 |   <- still here!
                                          +---+
                                          | 3 |   <- still here!
                                          +---+
                                          Size: 3  (dead weight)

  Add val 1:

  Deque:  | 7 | 1 |               Heap: {7, 5, 3, 1}
           +---+---+
  Size: 2                         Size: 4

  Total operations across n elements:
    Deque:  n pushes + n pops   = O(n)
    Heap:   n pushes x O(log n) = O(n log n)

The heap gives the same answers but at $O(n\log n)$ cost. For $n={10}^6$, that's $\sim 20\times$ more work.

Segment tree: It works—build in $O(n)$, query each window in $O(\log n)$, total $O(n\log n)$—but it's massive overkill for a problem that needs 4 lines of deque logic.

  Segment tree for sliding window min:
    Build:            O(n)
    Per window query: O(log n)
    Total:            O(n log n)
    Code:             ~40 lines
    Bug surface:      high (off-by-one in tree indexing)

  Monotonic queue:
    Total:            O(n)
    Code:             ~4 lines
    Bug surface:      low

The segment tree is the right tool when query endpoints are arbitrary. When the window slides one step at a time, the monotonic queue dominates in every dimension: time, code size, and debuggability.

std::queue: A std::queue only exposes the front and back. You need std::deque because you pop from both ends—dominated elements leave from the back, expired elements from the front.

  std::queue<T>:    push_back Y   pop_front Y   pop_back N  <- BROKEN
  std::deque<T>:    push_back Y   pop_front Y   pop_back Y  <- correct

Common Mistakes & Debugging

Store indices, not values. If you store values, you can't tell when the front element has left the window. This is the #1 beginner mistake.

Off-by-one in the expiry check. The front is expired when dq.front() <= i - k (0-indexed), equivalently dq.front() < i - k + 1. Trace it with $k=1$ to verify—that's the pathological case that catches most off-by-one errors.

Check dq.empty() before dq.front(). If all elements have been popped, accessing front() is undefined behavior. In the standard template, the deque is never empty at the front-read (you just pushed), but in DP variants where i starts from 1 you can hit this.

Min vs. max confusion. Max-queue pops back while a[dq.back()] <= a[i] (non-increasing deque). Min-queue pops while a[dq.back()] >= a[i] (non-decreasing deque). Get this backwards and the answers are garbage that looks plausible.

DP push order matters. The correct order is: expire front → read dp[dq.front()] → compute dp[i] → back-pop → push i. Pushing before computing dp[i] plants an uninitialized value in the deque and poisons every subsequent transition.

1-indexed vs. 0-indexed arrays. If your array is 1-indexed, the expiry condition dq.front() <= i - k still holds—but double-check your loop bounds.

Multiple queries with different $k$. The deque is not reusable across different window sizes. Rebuild per query, or use a sparse table for $O(1)$ arbitrary-range min/max after $O(n\log n)$ preprocessing.

---

Self-Test

Can you answer these without looking back?

• [ ] Why must you store indices in the deque, not values? What breaks if you store values?
• [ ] What single character changes in the pop_back condition to switch from max-queue to min-queue?
• [ ] Walk through array [4, 2, 7, 3] with $k=2$: write the deque contents after each step.
• [ ] Why is the amortized cost $O(1)$ per element, not $O(k)$? State the two-door argument in one sentence.
• [ ] In the DP pattern dp[i] = min(dp[j]) + cost[i] for $j\in [i-k,i-1]$, do you check front expiry before or after the push? Why does it matter?
• [ ] When would you use two monotonic queues together on the same array?
• [ ] A teammate says "just use priority_queue, same thing." Give the complexity argument for why it's not.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Sliding Window	Luogu P1886	Easy	Direct sliding window min and max
2	Sliding Window Maximum	CSES	Easy	Straightforward max in each window
3	Queries About Less or Equal Elements	CF 600B	Easy	Sort + sliding technique
4	Deque	CF 1579E2	Medium	Greedy with deque properties
5	Keshi Is Throwing a Party	CF 1610C	Medium	Binary search + greedy check
6	Knapsack for All Segments	CF 1442B	Medium	DP with range transitions
7	Minimum Cost to Make All Characters Equal	CF 1846E	Medium	DP optimization on windows
8	Gardener and the Array	CF 1582D	Medium	Window analysis
9	The Bakery	CF 834D	Hard	DP + segment tree / monotonic queue
10	Fence	CF 487B	Hard	DP with monotonic queue optimization

Further Reading

• cp-algorithms: Minimum stack / Minimum queue—covers the monotonic queue pattern and its DP applications.
• CF Blog: Monotonic Queue by adamant—concise tutorial with problem links.
• KACTL Sliding Window—reference implementation from KTH's ICPC notebook.
• Monotonic Stack—closely related; no element expiry, used for next-greater/next-smaller problems.
• Segment Tree—more general range queries, but $O(n\log n)$ vs $O(n)$ for the sliding window case.
• Data Structure Selection Guide—deciding which DS to reach for.
• Data Structures Ladder—practice problems organized by difficulty.

---