Monotonic stacks and deques

Why it matters

"For each element, find the next one that is larger" seems to need a nested loop. A monotonic structure answers it for all elements in O(n) by discarding candidates that can never matter again. The same idea handles spans, histograms, window maxima and some dynamic programs, and it is a good test of whether you can reason about what a data structure no longer needs to remember. Monitoring code uses it to keep a rolling maximum without storing the whole window.

Core ideas

Pattern: Monotonic stack. Scan left to right with a stack of indices whose values do not increase from bottom to top. When a[i] arrives, pop every index whose value is smaller: a[i] is the next greater element for each of them. Then push i.

ans = [-1] * n
stack = []                        # indices; values non-increasing upward
for i in range(n):
    while stack and a[stack[-1]] < a[i]:
        ans[stack.pop()] = i      # i is the next greater index
    stack.append(i)

Invariant: the stack holds exactly the indices still waiting for a greater element. A popped index is resolved, and it can never be the answer for anything further right, because a[i] is both larger and closer. Each index is pushed and popped at most once, so the loop is O(n) despite the inner while. Variants follow by flipping the comparison (next smaller), scanning right to left (previous greater), or running 2n iterations with indices modulo n for circular arrays. Daily Temperatures records distances; Online Stock Span keeps compressed spans on the stack in a streaming interface.

Spans and histograms. In Largest Rectangle in Histogram, the best rectangle that uses bar j at full height extends until a strictly lower bar on each side. Keep an increasing stack: when bar i pops bar j, i is j's right boundary and the new top is its left boundary. A sentinel bar of height 0 at the end flushes the stack. Trapping Rain Water can be solved the same way, or with two pointers and running maxima. Contribution counting (Sum of Subarray Minimums) multiplies, for each element, the number of choices of left end and right end for which it is the minimum: (distance to the previous smaller) × (distance to the next smaller). With duplicates, use a strict comparison on one side and a non-strict one on the other so that each subarray is counted once.

Pattern: Monotonic deque. For the maximum of every window of size k, keep a deque of indices with decreasing values. At each step, pop from the back while the back value is at most the new value (it is older and not larger, so the new element can always stand in for it), push the new index, pop from the front if it has left the window, and read the maximum at the front. Every index enters and leaves once: O(n), against O(n log k) for a heap with lazy deletion. Two deques, one for the maximum and one for the minimum, let a variable window check "max minus min at most limit".

Prefix-sum deques. Shortest Subarray with Sum at Least K allows negative numbers, so a plain window fails. Keep a deque of prefix indices with increasing prefix values: pop from the front while the current prefix minus the front prefix reaches K (recording the length), and pop from the back while the back prefix is at least the current one.

Common misconceptions

• "A while loop inside a for loop makes it O(n²)." Each element is pushed and popped once, so the total work is O(n).
• "Store values on the stack." Store indices: you usually need distances or window bounds, and the value is one lookup away.
• "Ties do not matter." With duplicates, strict versus non-strict comparisons decide which element owns a subarray; inconsistent choices double-count or miss subarrays.
• "A heap is just as good for window maxima." A heap needs lazy deletion and costs O(n log k); the deque is O(n).
• "Monotonic stacks only find next greater elements." The same discard argument covers spans, histograms, contribution counts and some dynamic programs.

How to approach it

Ask what a new element makes irrelevant. If it makes earlier smaller elements useless as future answers, keep a decreasing structure. Decide what you store (indices), the order, the pop condition including ties, and whether you record answers when popping or when pushing. Test increasing, decreasing and all-equal inputs. Interviewers typically check the amortized argument and the handling of duplicates.