Monotonic Stack

TL;DR

A monotonic stack is a stack you keep sorted in one direction — strictly increasing or strictly decreasing from bottom to top. Before you push a new element, you pop everything that breaks the invariant. Each pop is the moment you’ve found something about the popped element: its next greater neighbor, its previous smaller neighbor, the right boundary of the rectangle it anchors.

That single trick collapses a whole family of “for each element, scan forward until condition” problems from O(n²) to O(n). Next greater element, daily temperatures, largest rectangle in histogram, stock span, sum of subarray minimums — all the same skeleton with the direction of monotonicity flipped.

The amortized argument is what gives you O(n): every index is pushed at most once and popped at most once across the entire run, so the inner while loop’s total work over the whole array is O(n), not O(n) per element.

If you store values on the stack you’ll lose position information the moment the problem asks “how far away” or “what index”. Store indices; read values via arr[i] when you need them. This is the single most useful habit to build.

When to reach for it

Strong signals:

• The problem says “next greater”, “next smaller”, “previous greater”, “previous smaller”, or some span/distance to one of those.
• You’re computing, for each i, an answer that depends on the first j > i (or j < i) where some monotonic condition flips.
• A histogram, skyline, or rectangle-under-bars geometry.
• Brute force is a nested loop where the inner loop walks until it hits a comparison, then breaks.

Anti-signals:

• You need all j satisfying a condition, not just the first one — that’s segment tree or BIT territory.
• The condition isn’t monotonic in the value (e.g. “next prime”, “next index with same parity”) — a stack invariant won’t hold.
• You need random access by rank within the kept set — use a sorted container or heap.

Flavor 1 — next greater element (Daily Temperatures)

For each day, how many days until a strictly warmer one? Return 0 if none.

The stack holds indices of days whose answer is still unknown, kept in strictly decreasing temperature from bottom to top. When today’s temperature beats the top of the stack, that top day’s answer is i - top, and we pop it. Repeat until the stack invariant holds, then push today.

def daily_temperatures(t: list[int]) -> list[int]:
    n = len(t)
    out = [0] * n
    stack: list[int] = []   # indices, t[stack] strictly decreasing top-down
    for i, temp in enumerate(t):
        while stack and t[stack[-1]] < temp:
            j = stack.pop()
            out[j] = i - j
        stack.append(i)
    return out

Worked example. t = [73, 74, 75, 71, 69, 72, 76, 73].

Final out = [1, 1, 4, 2, 1, 1, 0, 0]. Indices 6 and 7 never get popped (no future day is hotter), so they keep the default 0. That’s the role of “unmatched leftovers on the stack” — they’re the elements with no answer.

Flavor 2 — largest rectangle in histogram

For each bar, find the widest rectangle that uses it as the shortest bar. The width is bounded on the right by the first shorter bar to the right, and on the left by the first shorter bar to the left. Both boundaries fall out of a single pass with an increasing stack of indices.

The clean trick: append a sentinel 0 to the end of the heights so every remaining bar gets popped and measured before the loop finishes. (You can also prepend a sentinel or wrap the loop in a final flush — sentinel is shorter.)

def largest_rectangle(heights: list[int]) -> int:
    h = heights + [0]                 # right sentinel forces final flush
    stack: list[int] = []             # indices, h[stack] strictly increasing
    best = 0
    for i, x in enumerate(h):
        while stack and h[stack[-1]] > x:
            top = stack.pop()
            left = stack[-1] if stack else -1   # index of previous shorter
            width = i - left - 1
            best = max(best, h[top] * width)
        stack.append(i)
    return best

When we pop top, the bar at h[top] is bounded on the right by i (the first shorter bar to the right, by the invariant) and on the left by stack[-1] after the pop (the bar still on the stack is the previous shorter, again by the invariant). So width = i - left - 1.

Worked example. heights = [2, 1, 5, 6, 2, 3]. After appending the sentinel: h = [2, 1, 5, 6, 2, 3, 0].

Answer: 10, the rectangle made of bars at indices 2 and 3 (heights 5 and 6, both at least 5, width 2, area = 5 × 2). The sentinel at i = 6 is what finally clears bars 5, 4, and 1 off the stack.

Why it works — the invariant

The invariant on the decreasing-stack version: for any two indices a and b on the stack with a below b, arr[a] > arr[b]. When a new value arrives that breaks this — arr[i] >= arr[stack[-1]] — the top is exactly the element whose “next greater (or equal)” is i. Pop, record, repeat. The increasing-stack version is the same thing with < flipped.

The O(n) bound is an amortized argument, not a per-step one. The inner while can pop several elements in one outer iteration, so locally the work isn’t constant. Globally it is: every index is pushed exactly once (one push per outer iteration) and popped at most once (because once popped, it’s gone). Total pushes ≤ n, total pops ≤ n, total work O(n). The outer loop also runs n times. Sum: O(n).

This is the same accounting trick that gives amortized analysis its name — charge the “expensive” inner pops to the elements being popped, each of which already paid for its push, so the total bill is bounded.

Complexity

• Time: O(n). One pass over the array; amortized O(1) work per element.
• Space: O(n) for the stack in the worst case (a strictly monotonic input never pops until a sentinel arrives, so the stack grows to n).

Common pitfalls

• Storing values instead of indices. As soon as the problem asks “how many days”, “what width”, or “which position”, you need the index. Always push indices and look up values via arr[i].
• Forgetting the end-of-array flush. With no sentinel and no post-loop drain, indices left on the stack never get measured — their answers stay at the default. For “next greater” that’s correct (no answer exists); for histogram-style problems it’s a silent bug. Use a sentinel or an explicit drain.
• Wrong direction of monotonicity. “Next greater” wants a decreasing stack (so a larger arrival can pop the smaller tops). “Next smaller” wants an increasing stack. Get this backwards and you’ll either pop nothing or pop everything.
• Strict vs non-strict comparison. “Strictly greater” is arr[i] > arr[stack[-1]]. If you write >= you’ll pop equals, which gives wrong answers for problems like Next Greater Element (where ties should not match) and double-counts for sum-of-minimums problems. Decide once, write it down, stay consistent.
• Mixing index and value on the same stack. Tuples like (i, arr[i]) work but are usually wasteful — you already have arr. The one exception is online problems (Stock Span) where you compress runs by storing (value, span) pairs.

Where you see this in production

• Compiler expression parsing. The shunting-yard algorithm uses an operator stack kept monotonic in precedence — when an incoming operator has lower or equal precedence than the top, the top is popped and emitted. The same monotonic-stack discipline is what produces correct postfix output in one pass.
• Browser layout — float and inline-block stacking. Layout engines (Blink, WebKit) maintain stacks of unresolved boxes whose final position depends on the next box’s measured size. When a wider/taller box arrives, smaller pending boxes get resolved and popped, exactly the next-greater-element pattern over a stream of layout boxes.
• Tick-stream “rolling max” feeds. Limit-order-book and market-data systems use a monotonic deque (the same idea, two-ended) to maintain the max price in a sliding window of the last k ticks in O(1) amortized per tick — the kdb+/Q mmax and most C++ HFT order-book maintainers ship this.
• GPU shader compiler register allocation. Live-range analysis pops spilled registers off a monotonic-by-priority stack as new uses come into scope, an exact analogue of the histogram pop-and-measure pattern over register pressure rather than bar height.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.