Stack

Stack Patterns

A stack is the right structure whenever the most recent unresolved thing is the one you need next. That covers nesting, where an inner bracket must close before an outer one, and it covers the monotonic stack, where you hold indices whose answers are still unknown until a larger or smaller value arrives. The monotonic variant is the one that separates candidates, because it turns several O(n squared) problems into a single linear pass.

3 patterns9 techniquesJava code

Where to start, and what comes next

01
Parentheses / Matching
Matching and nesting, which is the most intuitive use of a stack and the easiest place to see why the structure fits.
Valid Parentheses Decode String Min Remove to Make Valid
02
Expression Evaluation
Expression evaluation, where the stack holds operands or deferred context. Postfix first, then the parenthesised calculator.
Reverse Polish Notation Basic Calculator
03
Monotonic Stack
The hardest and most valuable pattern here. Next greater element, largest rectangle and trapping rain water are all the same idea.
Next Greater Element Largest Rectangle in Histogram Trapping Rain Water Stock Span

If you only have time for three things

The monotonic stack, and specifically that it holds indices rather than values so that widths can be computed from the index below it.
The observation that every index is pushed once and popped at most once, which is why an inner while loop still leaves the algorithm O(n).
Using ArrayDeque rather than the legacy Stack class.

In an interview

Monotonic stack problems are usually presented without any hint that a stack is involved, so the recognition is the test. The signal is a question about the next or previous element satisfying some comparison. If you find yourself writing a nested loop that scans forward for the next larger value, that is the moment to stop and reach for the stack.

The idea underneath

Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).

Problems that use these patterns

Valid ParenthesesNext Greater ElementLargest Rectangle in HistogramTrapping Rain WaterDaily TemperaturesDecode String

Head to head

Stack vs Queuelast in, first out against first in, first out Two Pointers vs Sliding Windowtwo indices moving under a rule against a contiguous range that grows and shrinks

Questions people ask

Why not use java.util.Stack?

It extends Vector, so every method is synchronised and slower, and it iterates from the bottom up, which is the opposite of pop order and has caused a lot of confusing bugs. The Javadoc itself recommends ArrayDeque.

Why does a monotonic stack store indices?

Because the answer usually needs a distance or a width, not just a value. With indices you get the width from the index remaining below after a pop, which is information a stack of values throws away.

How is it O(n) with a nested loop?

The inner loop only pops, and each index can be popped at most once across the entire run. Total pops are bounded by total pushes, which is n, so the work is linear no matter how the loop looks.