Lifespan & Expiration

Two Ways to Become Obsolete

In the last lesson, we saw the deque in action. Now let's zoom in on the idea that makes it tick, because this is the conceptual core of the entire chapter.

The monotonic queue has two pop conditions. Not one — two. And they exist for completely different reasons.

Back Pop: Eclipse

This one you already know from Chapter 1. When a new element arrives, it might make older elements irrelevant.

Think of it this way: if you're tracking the minimum and a new element is smaller than what's sitting at the back of the deque, those back elements will never be the answer. The new element is both smaller and newer — it'll outlast them in the window and dominate them on value. They've been eclipsed.

So we pop them off the back. Same logic as the monotonic stack. Nothing new here.

The eclipse pop is about value dominance. A stronger candidate showed up and rendered the weaker ones pointless.

Front Pop: Expiration

This is the new idea. And it's the reason we need a deque instead of a stack.

Even if an element has the best value in the deque — even if it's the current minimum or maximum — it can still become irrelevant. How? It ages out. Its index falls behind the left edge of the sliding window, and it no longer belongs.

You can't access the front of a stack efficiently. But a deque gives you O(1) access to both ends. So before processing each new element, you glance at the front: "Are you still inside my window?" If not, you're gone.

The expiration pop is about time relevance. The element didn't lose on value — it lost on age.

Dual pop conditions: eclipse removes dominated elements from the back, expiration removes aged-out elements from the front

A Tricky Example: When the Best Element Ages Out

Let's make this concrete. This is the scenario that trips people up.

Array: [2, 1, 4, 5, 3, 7], K = 3, tracking the minimum.

We maintain an increasing deque.

i = 0, a[i] = 2: Push 0. Deque: [0(2)].

i = 1, a[i] = 1: Eclipse: 2 >= 1, pop. Push 1. Deque: [1(1)].

i = 2, a[i] = 4: No eclipse (1 < 4). Push 2. Deque: [1(1), 2(4)]. Window [2,1,4]. Min = 1.

i = 3, a[i] = 5: Expiration: front is 1, window is [1,3]. Index 1 is in range. No eclipse (4 < 5). Push 3. Deque: [1(1), 2(4), 3(5)]. Window [1,4,5]. Min = 1.

i = 4, a[i] = 3: Expiration: front is 1, window is [2,4]. Index 1 is out! Pop the front. Now deque is [2(4), 3(5)]. Eclipse: 5 >= 3? Yes, pop. 4 >= 3? Yes, pop. Deque empty. Push 4. Deque: [4(3)]. Window [4,5,3]. Min = 3.

Here's what happened: the minimum was 1 for two consecutive windows. Then at i = 4, element 1 expired — its index fell outside the window. The new minimum isn't even something that was already in the deque. It's the element that just arrived (3), which also happened to eclipse everything left over.

The point: expiration can cause the answer to change even when no new "record-breaking" element shows up. The old champion simply timed out. The remaining candidates take over, and sometimes the newcomer sweeps them too.

The Chain Perspective

If you think in terms of the inequality chains from Chapter 1, here's the connection.

The monotonic stack maintained a chain — a sequence of elements with a monotonic relationship. New elements could shorten the chain from the tail by eclipsing weaker links.

The monotonic queue maintains the same kind of chain, but with a lifespan constraint. Each link in the chain has a birth time (its index), and links at the head of the chain can be trimmed when they exceed their lifespan (fall outside the window).

So the chain can be disturbed from two directions:

Tail: a stronger element arrives and chews up weak links (eclipse, same as the stack).
Head: the oldest link crosses the window boundary and gets trimmed (expiration, unique to the queue).

This dual-ended maintenance is exactly why we need a deque — a stack only gives us access to one end.

Max-Queue vs. Min-Queue

This works the same way as stacks:

Min-queue: maintains an increasing deque. Eclipse pops when back >= new. The front holds the minimum.
Max-queue: maintains a decreasing deque. Eclipse pops when back <= new. The front holds the maximum.

The only difference is the comparison direction. The expiration logic is identical for both — it's purely index-based and doesn't care about values.

Packaging It as a Class

Sometimes you don't want to manually manage the deque inside a loop. You want a clean abstraction: push a value, pop a value, query the max (or min). This is the "MaxQueue" (or "MinQueue") data structure.

The trick is tracking which logical index is being pushed and which is being popped. Here's the structure:

struct MaxQueue {
    deque<pair<int,int>> dq; // (value, index)
    int push_idx = 0;
    int pop_idx = 0;

    void push(int val) {
        // Eclipse: back values that are <= val will never be the max
        while (!dq.empty() && dq.back().first <= val)
            dq.pop_back();
        dq.push_back({val, push_idx});
        push_idx++;
    }

    void pop() {
        // Expire: only actually remove from deque if front is the one being popped
        if (!dq.empty() && dq.front().second == pop_idx)
            dq.pop_front();
        pop_idx++;
    }

    int getMax() {
        return dq.front().first;
    }
};

Notice the pop() method. It doesn't always remove from the deque. If the front element was already eclipsed earlier, it's not in the deque anymore — so pop() just increments pop_idx and moves on. The deque only stores surviving candidates.

This gives you amortized O(1) for all three operations. Each element enters the deque once via push and leaves at most once via either eclipse or expiration.

When to Use Which

A question you should always ask: "Am I maintaining a min-queue or a max-queue?"

The answer depends on what your problem needs from the window:

If you need the minimum over the window (like in sliding window min, or DP optimization where you want the best previous state), use a min-queue with an increasing deque.
If you need the maximum over the window, use a max-queue with a decreasing deque.

Sometimes you need both — for instance, finding windows where max minus min is within some bound. In that case, run two deques in parallel, one for min and one for max.

Try It

The starter code has a MaxQueue struct with the eclipse step left blank. Fill it in, then test it against the sliding window maximum problem: read N, K, and N integers, print the maximum of each window of size K.

If your implementation is correct, it'll match the output of the raw deque approach from lesson 1, but with a cleaner interface.