Sliding Window Min/Max

The Problem

You're given an array of N integers and a window of size K. Imagine sliding that window one position at a time from left to right. At each position, you need the minimum element inside the window.

For a small array, you could just scan every window in O(K) time. That gives O(NK) total. When N is a million and K is half a million, that's way too slow.

We need O(N). And the monotonic queue gives us exactly that.

Why the Stack Isn't Enough

In Chapter 1, the monotonic stack was perfect for "next greater element" style problems. You pushed elements on, popped when the new element broke the monotonic order, and that was it. Every element entered and left the stack at most once.

But here's the catch: the stack has no notion of time. An element sits on the stack until something bigger (or smaller) pushes it off. It could linger there forever.

In a sliding window, elements don't get to linger. Once an element's index falls outside the window, it's irrelevant — no matter how good its value is. The stack doesn't know about this. It only cares about value comparisons, not position boundaries.

We need a data structure that does both: maintains monotonic order by value and evicts elements that have aged out of the window.

Enter the Deque

A deque (double-ended queue) lets you push and pop from both ends. That's the key.

Back end: works just like the monotonic stack. When a new element arrives, pop anything from the back that it dominates.
Front end: this is new. Before processing each element, check if the front of the deque has fallen outside the window. If so, pop it.

We store indices in the deque, not values. This way we can check whether the front index is still inside the window, and we can look up the corresponding value in the original array whenever we need it.

Stack vs Deque: the deque allows push and pop from both ends, enabling expiration from the front and eclipse from the back

Walking Through an Example

Let's trace through the classic example.

Array: [1, 3, -1, -3, 5, 3, 6, 7], K = 3

The deque stores indices. I'll show the values in parentheses for clarity.

i = 0, a[i] = 1: No expiration check needed (window hasn't filled yet). Deque is empty, so nothing to eclipse. Push index 0. Deque: [0(1)]. Window not full yet — no output.

i = 1, a[i] = 3: Expiration: front is 0, window is [0, 2] — fine. Eclipse: back is 0(1), and 1 < 3, so 3 doesn't eclipse 1. Push index 1. Deque: [0(1), 1(3)]. Window not full yet — no output.

i = 2, a[i] = -1: Expiration: front is 0, window is [0, 2] — still fine. Eclipse: back is 1(3), and 3 >= -1? No. Back is 0(1), and 1 >= -1? No. Actually wait — -1 is smaller than both, so it doesn't eclipse anything. Push index 2. Deque: [0(1), 1(3), 2(-1)]. Window [0..2] is full. Answer: a[0] = 1.

Hmm, but -1 is the smallest. Why isn't it the answer?

Because the minimum of [1, 3, -1] is -1. Let me re-check. The front of the deque is 0(1). That's not right — the answer should be -1.

Here's the issue: I applied the eclipse condition wrong. Let's redo this properly.

For a minimum queue, we maintain an increasing deque. When a new element arrives, we pop from the back everything that's greater than or equal to it — because those elements will never be the minimum while the new, smaller element is in the window.

Let's redo from i = 2, a[i] = -1: Eclipse: back is 1(3). Is 3 >= -1? Yes. Pop it. Back is now 0(1). Is 1 >= -1? Yes. Pop it. Deque empty. Push index 2. Deque: [2(-1)]. Window [0..2] is full. Answer: a[2] = -1. Correct.

i = 3, a[i] = -3: Expiration: front is 2, window is [1, 3] — index 2 is in range. Eclipse: back is 2(-1). Is -1 >= -3? Yes. Pop it. Deque empty. Push index 3. Deque: [3(-3)]. Answer: a[3] = -3. Correct — window [3, -1, -3], min is -3.

i = 4, a[i] = 5: Expiration: front is 3, window is [2, 4] — index 3 is in range. Eclipse: back is 3(-3). Is -3 >= 5? No. Push index 4. Deque: [3(-3), 4(5)]. Answer: a[3] = -3. Window [-3, 5, 3]... wait, window is [-1, -3, 5], min is -3. Correct.

i = 5, a[i] = 3: Expiration: front is 3, window is [3, 5] — index 3 is in range. Eclipse: back is 4(5). Is 5 >= 3? Yes. Pop it. Back is 3(-3). Is -3 >= 3? No. Push index 5. Deque: [3(-3), 5(3)]. Answer: a[3] = -3. Window [-3, 5, 3], min is -3. Correct.

i = 6, a[i] = 6: Expiration: front is 3, window is [4, 6] — index 3 is out of range! Pop it from the front. Eclipse: back is 5(3). Is 3 >= 6? No. Push index 6. Deque: [5(3), 6(6)]. Answer: a[5] = 3. Window [5, 3, 6], min is 3. Correct.

This is the moment to notice: the minimum changed not because a smaller element arrived, but because the old minimum (-3) expired. That's the front-pop in action.

i = 7, a[i] = 7: Expiration: front is 5, window is [5, 7] — in range. Eclipse: back is 6(6). Is 6 >= 7? No. Push index 7. Deque: [5(3), 6(6), 7(7)]. Answer: a[5] = 3. Window [3, 6, 7], min is 3. Correct.

Final output: -1 -3 -3 -3 3 3

Sliding window trace showing deque state and output at each step of the example

The Four Steps

Every iteration follows the same four steps:

Expire — if the front of the deque is outside the window [i - k + 1, i], pop it from the front.
Eclipse — while the back of the deque is worse than (greater than or equal for min-queue) the new element, pop it from the back.
Push — push the current index onto the back.
Read — if we've seen at least K elements, the front of the deque is the answer.

Here's the complete code:

deque<int> dq; // stores indices
for (int i = 0; i < n; i++) {
    // 1. Expire
    if (!dq.empty() && dq.front() <= i - k)
        dq.pop_front();
    // 2. Eclipse
    while (!dq.empty() && a[dq.back()] >= a[i])
        dq.pop_back();
    // 3. Push
    dq.push_back(i);
    // 4. Read
    if (i >= k - 1)
        cout << a[dq.front()] << "\n";
}

For a maximum queue, just flip the comparison in the eclipse step: pop from the back while a[dq.back()] <= a[i].

Why It's O(N)

The amortized argument is identical to the monotonic stack. Each index enters the deque exactly once (one push_back) and leaves the deque at most once (either through a pop_back during eclipse or a pop_front during expiration). That's at most 2N deque operations total across the entire loop, so the total work is O(N).

Don't let the while loop inside the for loop fool you into thinking it's O(N^2). The while loop doesn't run N times per iteration — it runs at most N times total across all iterations combined.

Try It

The starter code in the editor reads N and K, then N integers. Fill in the expire and eclipse steps to print the sliding window minimum for each valid window. The four-step pattern above is all you need.

Once that works, try modifying it to print the sliding window maximum instead. The only thing that changes is one comparison operator.