Lesson 3 · Advanced structures and algorithms

Monotonic Queues

A monotonic queue applies the strictly sorted invariant of a monotonic stack to a double-ended queue (deque). It allows you to maintain the maximum or minimum value of a moving window in constant time.

The Sliding Window Maximum

Given an array and a window of size K sliding from left to right, you must find the maximum value in the window at each step. Naively scanning the window every time takes O(N * K).

We need a data structure that can add new elements, remove elements that fall out of the window, and report the current maximum, all in O(1) amortized time.

Naive approach is O(N * K)
Max Heap approach is O(N log K)
Monotonic Queue approach is O(N)

Why Stacks Fail Here

A monotonic stack can easily tell you the maximum element (it's at the bottom of a decreasing stack). However, as the window slides right, elements on the left expire and must be removed.

A stack only allows removal from the top. We cannot remove the expired maximum element from the bottom. This is why we must use a Deque, which allows popping from the front.

Stacks cannot remove expired elements
Deques can pop from the front (pop_front)
Combines stack pushing with queue popping

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.

Code example

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 <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;
}

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;
    }
}

InputArray: [1, 3, -1, -3, 5, 3], Window size K=3

OutputMaxes: [3, 3, 5, 5]

Example

Run the example step by step

Output

Maintaining the Queue

To insert a new element, we act like a monotonic stack: we pop_back any elements smaller than the new element, because they are useless (they are smaller AND older). Then we push_back the new element.

To handle the sliding window, we check the front of the queue. If the index at the front has expired (is outside the current window bounds), we pop_front.

pop_back smaller elements (maintain invariant)
push_back the new element
pop_front expired elements

The Front is the Answer

Because we strictly maintained a monotonically decreasing order, the largest element is always at the front of the deque. Because we pop_front expired elements, the front is guaranteed to be valid.

Therefore, at any step, the maximum value in the sliding window is simply deque.front(). Every element is pushed and popped at most once, yielding a total O(N) time complexity.

Front of deque is the window's maximum
Useless elements are naturally purged
Indices are stored, not values, to check expiration