Deques and monotonic stacks

Deques: both ends at once

A deque, short for double-ended queue and pronounced "deck", combines a stack and a queue: it supports push and pop at both the front and the back, all in O(1). The ring buffer from the previous lesson already has everything needed. Moving head backward, (head − 1) % capacity, adds at the front, just as moving forward removed from it. Java's ArrayDeque and Rust's VecDeque are growable ring buffers; Python's collections.deque stores items in a chain of fixed-size blocks instead.

Because a deque can behave as a stack, a queue or both, it is often the most useful single structure in this module. Java's documentation even recommends ArrayDeque over its older Stack class. Its main limitation is the same as a queue's: reading the middle is slower or unavailable.

This lesson's real subject, though, is a way of using a stack or a deque that turns several quadratic problems into linear ones.

The next greater element

Many problems ask, for every element of an array, about the next element that is bigger (or smaller) than it: the next warmer day, the next taller building, the next higher stock price. The direct approach scans forward from each position until it finds one, which is O(n²) when the array is falling for long stretches.

A monotonic stack answers all of them in one left-to-right pass. It holds the indexes of elements that are still waiting for their answer. Each new element is compared with the top of the stack:

• while the new element is greater than the element on top, the new element is the top's answer: pop the top and record it;
• then push the new element, which now waits for its own answer.

Because an element is popped as soon as something bigger arrives, the elements left on the stack always decrease from bottom to top. That ordering is what "monotonic" refers to.

The trace above runs it on the daily temperatures. Days 3 and 4, at 71 and 69, wait on the stack under day 2's 75. When day 5 brings 72, it answers both of them in one go, and stops at 75, which it doesn't beat. Day 6 brings 76 and answers the rest.

Why it is linear

The inner while loop can pop several items for one new element, so the code looks quadratic. The trick is to count the work per element instead of per pass of the outer loop. Each index is pushed exactly once. Each index is popped at most once, because once popped it is gone. So over the entire run there are at most n pushes and n pops: O(n) in total, with O(n) extra space for the stack in the worst case. This style of counting, total work over a whole sequence, is the amortized argument from the dynamic arrays lesson in a different setting.

The other half of the argument is correctness: nothing popped is ever needed again. An element is popped exactly when its answer arrives, so it is finished. And an element is never popped too early, because only a strictly greater value pops it.

Variations

Flip the comparison or the direction, and the same pattern answers related questions:

The hardest practice problem for this lesson, Largest rectangle in histogram, needs both the previous smaller and the next smaller bar for each bar: the widest rectangle that uses a bar's full height stretches between them. One increasing stack finds both at once, because when a bar is popped, the new bar is its next smaller and the bar beneath it on the stack is its previous smaller.

The sliding-window maximum

A monotonic deque extends the idea to a moving window. The problem: report the maximum of every window of k consecutive elements. Recomputing each window costs O(n·k).

Keep a deque of indexes whose values decrease from front to back. For each new element:

1. Pop from the back every index whose value is smaller than the new one. Those elements can never be a window's maximum again: the new element is bigger and will stay in the window longer.
2. Push the new index at the back.
3. Pop from the front if that index has slid out of the window.
4. The front is now the maximum of the current window.

Each index enters and leaves the deque once, so the whole scan is O(n), whatever k is. The same structure appears in stream processing and in dynamic programming optimizations later in this track. The next lesson turns to a stack you use in every program, whether you write one or not.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Deques and monotonic stacks from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function next_greater_elements(nums):
    n = length(nums)
    ans = array of size n filled with -1
    stack = empty_stack()  // stores indices with decreasing values
    for i from 0 to n - 1:
        while not stack.empty() and nums[stack.top()] < nums[i]:
            idx = stack.pop()
            ans[idx] = nums[i]
        stack.push(i)
    return ans

#include <vector>
 
std::vector<int> nextGreaterElements(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    std::vector<int> ans(n, -1), st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.back()] < nums[i]) {
            ans[st.back()] = nums[i];
            st.pop_back();
        }
        st.push_back(i);
    }
    return ans;
}

import java.util.*;
 
public class StackQueueSolver {
    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peekLast()] < nums[i]) {
                ans[st.pollLast()] = nums[i];
            }
            st.offerLast(i);
        }
        return ans;
    }
}

def next_greater_elements(nums: list[int]) -> list[int]:
    ans = [-1] * len(nums)
    stack: list[int] = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.