Monotonic Stack / Queue

Here is the mindset that unlocks this one: as you scan a sequence, most of the elements you are holding onto are already doomed, and the trick is to throw them out the instant you know it. A monotonic stack or queue is just a container you keep in sorted order by evicting any element that a newcomer has rendered useless. What survives is a short list of genuine candidates, and that is what turns a quadratic scan into a linear one.

The idea: throw away values that can never win

Take the classic question: for each day's stock price, what is the next day the price is higher? The brute force looks ahead from every day, which is O(n^2). The monotonic stack does it in one pass by holding only the days still waiting for a taller neighbor, kept in decreasing order:

def next_greater(prices):
    result = [-1] * len(prices)
    stack = []                       # indices, their prices decreasing down the stack
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] < price:
            result[stack.pop()] = price   # today is the answer for everyone shorter
        stack.append(i)
    return result

On [100, 80, 120, 90, 130] this returns [120, 120, 130, 130, -1]. The key move is the while: when today's price arrives, every waiting day shorter than it has just found its answer, so they pop off together. A day only lingers on the stack while nothing taller has come along, which means each index is pushed once and popped once. That is the whole reason it is O(n): the inner loop looks scary, but across the entire run it does at most n pops.

Bars of heights 100 80 120 90 130; for each bar an arrow points to the first taller bar on its right, so 100 and 80 both point to 120, 120 and 90 both point to 130, and 130 has none, which is the answer a decreasing monotonic stack produces in a single pass.

In the wild: the maximum in every rolling window

Swap the stack for a double-ended queue and the same eviction idea answers a question monitoring systems ask all the time: what is the peak value in every rolling window? Think of an autoscaler that needs the highest request rate over each moving five-minute span to decide whether to add capacity. Recomputing each window's max from scratch is O(n*k); a monotonic queue holds candidate indices with their values decreasing from front to back and answers it in O(n):

from collections import deque

def window_maxima(arr, k):
    q = deque()          # indices, arr values decreasing from front to back
    out = []
    for i, x in enumerate(arr):
        while q and arr[q[-1]] <= x:
            q.pop()                       # x outlives these and is bigger, drop them
        q.append(i)
        if q[0] == i - k:                 # the front just slid out of the window
            q.popleft()
        if i >= k - 1:
            out.append(arr[q[0]])         # the front is the window's maximum
    return out

It is the same instinct the stack used, applied at both ends. When a new value arrives, every smaller value still waiting is dead, because the newcomer is larger and will stay in the window at least as long, so you pop them from the back. The only thing the queue adds is evicting the front when it ages out of the window. Same principle of keeping just the live candidates, one extra bit of bookkeeping. On [1, 3, -1, -3, 5, 3, 6, 7] with k = 3 it yields [3, 3, 5, 5, 6, 7], the max of each rolling window, in a single sweep.

The trigger

For each element, you want the next or previous element that is greater or smaller, or you want the max or min of every sliding window. The giveaway is a nested loop that scans forward or backward from each position looking for the first element that beats it. That inner scan is exactly what the monotonic structure amortizes away.

Where it shows up

  • Next or previous greater/smaller element, and its dressed-up cousins like daily temperatures or stock spans.
  • Largest rectangle in a histogram, where a monotonic stack tracks bars whose extent is still undecided.
  • Sliding window maximum or minimum, the deque version above, common in signal and metrics processing.

Where it bites

The make-or-break decision is whether the comparison is strict. Using < versus <= when you pop controls how equal values are handled, and getting it wrong either drops a valid answer or keeps a stale one, which is the usual source of off-by-one bugs here. For the queue version, remember it stores indices, not values, precisely so you can tell when the front has aged out of the window; storing raw values throws that information away.

When monotonic logic does not fit

The pattern only pays off when a newcomer can cleanly retire the candidates before it: "this value is bigger and outlives them, so they are dead." With no such relation, forcing a stack to stay monotonic just wraps ceremony around an ordinary scan. It is built for next or previous greater and smaller, and for window extrema; if you need arbitrary order statistics, random access into the middle, or values that keep changing, a heap, a balanced tree, or a segment tree is the right home. Reaching for a monotonic stack everywhere is the classic hammer mistake, and the tell that you are making it is a pop condition you cannot quite explain.

Where it connects

The deque variant is the efficient engine inside a Sliding Window whenever the window's quantity is a max or min rather than a sum. It leans on ordinary Stack and Queue fundamentals, so be comfortable with those first. And it is a close relative of Two Pointers in spirit: both keep a small, moving frontier of live candidates instead of reconsidering everything from scratch.

References