Lesson 3 · Advanced structures and algorithms

Monotonic Queues

A monotonic queue is a deque kept in sorted order, holding only the values that could still become the maximum of a future window. Expired values leave the front, dominated values leave the back, and whatever sits at the front is the current window maximum — read in constant time.

The Problem a Stack Cannot Solve

Sliding window maximum asks for the largest value in every window of size k as it moves across an array. Recomputing each window costs O(n·k); a heap improves it to O(n log k); a monotonic queue achieves O(n).

The reason the ordinary structures fall short is worth being precise about, because it explains the design.

A plain maximum variable fails because the maximum can leave the window. Once it does, the next largest value must be found, and there is no way to recover it — the variable retained no other candidates. This is the same non-invertibility that stops prefix sums from answering range minimum queries.

A monotonic stack fails for a different reason. A stack removes the most recently added element, but a sliding window expires the oldest element. The one that must leave is at the bottom of the stack, unreachable without emptying it.

A heap works but overshoots. It gives O(log k) per operation and, more awkwardly, offers no way to remove a specific expired element — implementations resort to lazy deletion, popping stale entries when they surface at the top.

What the problem actually requires is removal at both ends: discard candidates that are dominated (from one end) and candidates that have expired (from the other). That is a deque, and using both ends for these two distinct jobs is the entire technique.

A single max variable cannot recover the next best when the max expires
A stack removes the newest; a window expires the oldest
A heap works at O(log k) but cannot delete a specific element
Two different removals are needed, so the structure must be a deque

The Two Rules

The deque holds indices, and is maintained so that the values at those indices are in decreasing order from front to back. Two rules preserve that, applied in order at every step.

Rule one — expire from the front. Before reading the answer, remove the front index if it has fallen outside the window, that is if front <= i - k. At most one index expires per step, since the window advances by one.

Rule two — filter from the back. Before pushing index i, repeatedly remove indices from the back while the value at the back is less than or equal to the value at i. Then push i.

Rule two is where the reasoning lives. If an earlier element is smaller than the current one, it can never be the maximum of any future window — because every window still containing it also contains the current element, which is both larger and expires later. It is dominated on both counts, so it is discarded permanently rather than kept as a fallback.

That double justification — larger and longer-lived — is the correctness argument, and it is what an exam answer needs. Neither property alone would suffice.

Indices, not values, because rule one tests position. With values stored there is no way to know whether the front has left the window.

Use <= rather than < when duplicates matter: popping equal values keeps the deque shorter and is safe, since the later of two equal elements survives longer and serves just as well. Either works for correctness on maximum queries; <= is tidier.

For sliding window minimum, reverse the comparison and maintain an increasing deque. Everything else is unchanged.

Expire the front when front <= i - k
Pop the back while its value is ≤ the arriving value, then push
A dominated element is both smaller and shorter-lived — discard it
Store indices, since expiry is tested by position

Why the Front Is Always Correct

After both rules have been applied, the value at the front index is the maximum of the current window, available in O(1). Establishing why closes the argument.

Rule one guarantees everything in the deque is inside the window — nothing expired remains. Rule two guarantees the values are in decreasing order, so the front holds the largest of them. What must still be shown is that nothing was discarded that should have been kept.

Rule two only ever removes an element when a larger element arrives later. Any window containing the discarded element from that point on also contains the larger, later one. So the discarded element could not have been the maximum of any remaining window — removing it loses nothing.

Together: the deque contains exactly the elements that could still be the maximum of some future window, in decreasing order. Its front is therefore the current maximum, and the structure is often called the set of candidates.

A useful way to picture it: the deque holds a decreasing staircase of values, with the tallest at the front. New arrivals knock down everything shorter behind them, and the window's advance erodes the front.

Note that the deque's contents are not the window. It is a subset — the window may hold k elements while the deque holds one, if that element dominates all the others. The deque never exceeds k entries, giving O(k) space rather than O(n).

Rule one leaves only in-window indices; rule two orders them decreasing
A discarded element is dominated in every window that remains
The deque holds exactly the still-possible maxima, in order
It is a subset of the window, never larger than k — O(k) space

Key reference

Terms, operations, and practical uses

Core concept

Deque FoundationA monotonic queue requires a Deque because it must pop from the back to maintain order, and pop from the front to expire old elements.
Sorted InvariantLike a monotonic stack, the elements inside the deque must strictly follow an increasing or decreasing trend.
ExpirationRemoving elements from the front of the deque because they have fallen out of the sliding window bounds.

Maintenance operations

Push Back (Purge)Removing smaller/older elements from the rear of the deque before inserting a new element, as they can never be the maximum again.
Pop Front (Expire)Checking if the index at the front of the deque is too old for the current window and removing it.
Front AccessRetrieving the absolute maximum (or minimum) of the current window simply by looking at the front of the deque.

Algorithmic uses

Sliding Window MaximumThe textbook application. Given an array and a window size K, find the maximum in every window in O(N) time.
Shortest Subarray with Sum at Least KA complex problem combining Prefix Sums with a Monotonic Queue to find optimal bounds.
Dynamic Programming OptimizationUsing monotonic queues to optimize state transitions in 1D DP problems that have a sliding window constraint.

Implementation

Sliding Window Maximum

from collections import deque

def maxSlidingWindow(nums, k):
    q = deque() # Stores indices
    ans = []
    for i, n in enumerate(nums):
        # Expire old elements
        if q and q[0] < i - k + 1:
            q.popleft()
        # Maintain monotonic decreasing property
        while q and nums[q[-1]] < n:
            q.pop()
        q.append(i)
        # Record max once window is fully formed
        if i >= k - 1:
            ans.append(nums[q[0]])
    return ans
print('Maxes:', maxSlidingWindow([1, 3, -1, -3, 5, 3], 3))

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> q;
    vector<int> ans;
    for (int i = 0; i < nums.size(); i++) {
        if (!q.empty() && q.front() < i - k + 1) q.pop_front();
        while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();
        q.push_back(i);
        if (i >= k - 1) ans.push_back(nums[q.front()]);
    }
    return ans;
}
int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3};
    vector<int> ans = maxSlidingWindow(nums, 3);
    cout << "Maxes: [";
    for (size_t i = 0; i < ans.size(); i++) {
        if (i) cout << ", ";
        cout << ans[i];
    }
    cout << "]\n";
}

import java.util.*;
class Main {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> q = new ArrayDeque<>();
        int[] ans = new int[nums.length - k + 1];
        int ansIdx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!q.isEmpty() && q.peekFirst() < i - k + 1) q.pollFirst();
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) q.pollLast();
            q.offerLast(i);
            if (i >= k - 1) ans[ansIdx++] = nums[q.peekFirst()];
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] ans = new Main().maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3}, 3);
        System.out.println("Maxes: " + Arrays.toString(ans));
    }
}

Watch it run

Step through it

Running on Array: [1, 3, -1, -3, 5, 3], Window size K=3

Output

Read all 9 Steps

Index 0 — value 1 The deque stores indices, not values, so we can tell when one falls out of the window. Push index 0; the window is not full yet.
Index 1 — 3 evicts 1 3 arrives and is both larger and newer than 1, so index 0 can never be a future maximum. pop_back it and push index 1.
Index 2 — first full window −1 < 3, so it stays: it may become the max once 3 expires. Window [1,3,−1] is complete and the answer is the front, 3.
Index 3 — window slides −3 < −1, so it is appended behind. Window [3,−1,−3] gives max 3 again — read straight off the front in O(1).
Index 4 — the front expires The window is now [2..4], and index 1 is outside it. This is why a stack fails here: we must drop from the FRONT, which only a deque allows.
Index 4 — 5 clears the back 5 beats −3 and then −1, so both pop from the back. Each index leaves the deque at most once, which is what keeps the total O(N).
Index 5 — 3 is kept 3 < 5, so it is not useless: when 5 expires, 3 is next in line. Window [−3,5,3] reports 5.
Why the front is always right The deque is kept strictly decreasing, so the largest live value sits at the front; expired indices are dropped before reading. Both invariants together make front() the answer.
All four windows reported A heap would cost O(N log K) and leave stale entries to clean up; the deque does it in O(N) time and O(K) space.

Cost, and Where the Pattern Appears

The complexity argument mirrors the monotonic stack's. Each index is pushed exactly once, at its own iteration, and popped at most once — from either end. So the total number of removals across the whole run is bounded by n, regardless of how many happen in any single step.

The inner while loop therefore contributes O(n) in total, not O(k) per step, making the algorithm O(n) time. Space is O(k).

Compared with the alternatives: brute force is O(n·k), a heap with lazy deletion is O(n log k) and O(n) space in the worst case, and a balanced BST as a multiset is O(n log k). The monotonic deque is strictly better on both counts, which is why it is the expected answer.

The pattern generalises beyond finding a maximum. Whenever a sliding window needs the extreme of its contents, and that extreme cannot be maintained incrementally because removal is not invertible, a monotonic deque is the tool.

Shortest subarray with sum at least k, on an array that may contain negative numbers, is the significant case. Ordinary two-pointer sliding windows fail there because negatives break the monotonicity the technique depends on. The solution runs a monotonic deque over the prefix sums, maintaining them in increasing order, and it is the standard example of the pattern solving something a plain window cannot.

Constrained dynamic programming is the other family: recurrences of the form dp[i] = max(dp[j]) + cost where j ranges over a sliding window. Evaluating the max naively makes the DP O(n·k); a monotonic deque reduces it to O(n). The 'jump game' variants where a jump length is bounded are the common instance.

Also worth naming: collections.deque in Python and ArrayDeque in Java are the right structures to implement this with, both giving O(1) operations at each end. Using a list and pop(0) reintroduces an O(n) removal and quietly restores the quadratic behaviour the algorithm was designed to avoid.

Push once, pop once per index — O(n) time, O(k) space
Beats the heap solution on both time and space
Solves shortest-subarray-sum problems that plain windows cannot
Reduces window-constrained DP recurrences from O(n·k) to O(n)