Stacks & Monotonic Stack

Last in, first out — the shape of nesting, undo, and "what's the next bigger thing?"

intermediate~55 min4 simulations12 problems

▶ guided lesson ⚡ 1-minute summary ↻ 15 recall cards

before this: Big-O · Java Toolkit · Arrays & Strings · Recursion

Section

01 · why it exists

Why this exists, and the weight it carries

since1955–1960

Stack (last in, first out)

Friedrich L. Bauer & Klaus Samelson

In Munich, from 1955, Bauer and Samelson wanted to translate formulas like a × (b + c) into machine code in one left-to-right pass. Their trick: put each operator that can't run yet into a "Keller" (German for cellar) and take out the most recent one first. They filed a German patent on this principle on 30 March 1957, and described it in English in "Sequential formula translation" (CACM, 1960). Bauer's 1988 IEEE Computer Pioneer Award reads simply: "For computer stacks."

the problem it solvedTranslating formulas with nested parentheses and operator precedence in one left-to-right pass, by postponing each operator until it can be applied.

its jobs today

Every Java method call: the JVM pushes a frame on the thread's stack and pops it on return (see the call stack in the Recursion chapter).
Undo in editors (Ctrl+Z) and the browser's Back button: the most recent change or page comes off first.
Parsers, compilers and linters: matching brackets and tags, and turning expressions into code.

the weight it carries

Illustrative: checking the brackets of a 10⁶-character JSON file. With a stack: one pass, at most 10⁶ pushes and pops. Deleting matched pairs until nothing changes: on deep nesting, about n²/4 = 2.5·10¹¹ character copies.

without it

Every "most recent first" job — nesting, undo, method calls — would need its own bookkeeping, and bracket checks would be quadratic.

when · why · how

when: The most recent unfinished thing must be handled first: an open bracket, a pending operator, an undo step, a [ waiting for its ].
why: push, pop and peek touch only the top — O(1) each (amortized for an array) — so one left-to-right pass is O(n) time, with O(n) space in the worst case.
how: Deque<Character> stack = new ArrayDeque<>(); with push, pop, peek and isEmpty(); an int[] plus a top index in hot loops.

since1924–1957

Reverse Polish notation & the operand stack

Jan Łukasiewicz; Charles L. Hamblin

Logician Jan Łukasiewicz came up with a parenthesis-free notation in 1924 (published 1929): write each operator before its operands. Computer builders turned it around — operator after its operands. Burks, Warren and Wright used such a notation for a logic machine in 1954. In 1957 Charles Hamblin in Australia independently paired this reverse Polish notation with a stack, so machine instructions needed no addresses. The JVM still works this way: iadd pops two ints from the operand stack and pushes their sum.

the problem it solvedEvaluating arithmetic without parentheses or precedence rules: every operator simply uses the two most recent values.

its jobs today

The JVM: each method frame has an operand stack, so a + b runs as iload, iload, iadd — postfix evaluation.
Calculators and formula engines: parse the infix formula into postfix (Dijkstra's shunting-yard algorithm), then evaluate it with one stack.

the weight it carries

Illustrative: a postfix expression of 9,999 tokens (5,000 numbers, 4,999 operators). With a stack: one step per token — a number is one push, an operator two pops and one push — and at most 5,000 numbers ever wait. Collapsing the first operator again and again in an ArrayList: up to 4,999 collapses × 10⁴ tokens ≈ 5·10⁷ element shifts.

without it

Evaluators would need parentheses and precedence tables at run time, and bytecode would have to name a register for every value.

when · why · how

when: Postfix tokens, a calculator, or any "apply this to the two latest values" rule.
why: O(1) stack work per token → O(n) time; O(n) space for the waiting numbers.
how: Deque<Integer> st = new ArrayDeque<>(); Number → push. Operator → int b = st.pop(), a = st.pop(); st.push(a op b); — the right operand comes off first.

since?

Monotonic stack

The one-pass stack for "nearest bigger / smaller value" is folklore — we found no inventor to credit. Under the name "all nearest smaller values", the problem was studied on parallel computers by Berkman, Schieber and Vishkin (Journal of Algorithms, 1993).

its jobs today

Time-series questions answered for every point in one pass: the next higher price, the days until a warmer reading, a price's "span".
Geometry on bars and grids: the largest rectangle under a histogram, and row by row, the largest all-1 rectangle in a binary image or seat map.

the weight it carries

Illustrative: 10⁵ daily readings. Brute force on a falling series: n(n − 1)/2 ≈ 5·10⁹ comparisons. Monotonic stack: each index is pushed once and popped at most once — at most 2·10⁵ stack operations.

without it

Every "next greater" or "nearest smaller" question would be an O(n²) scan.

when · why · how

when: For every element you need the nearest element to one side that beats it (bigger or smaller), or how far it can stretch.
why: O(n) total — at most n pushes and n pops — instead of O(n²); O(n) extra space for the stack.
how: A stack of indices: while (!st.isEmpty() && nums[st.peek()] < nums[i]) ans[st.pop()] = nums[i]; st.push(i); Flip < to > for next smaller.

since1996 · 2006

ArrayDeque (and why not java.util.Stack)

Java 1.0 team (Stack); Josh Bloch & Doug Lea (ArrayDeque, Java 6)

Java 1.0 shipped java.util.Stack as a subclass of Vector: every method is synchronized, and inherited methods like get(i) let code reach into the middle. Java 6 added the Deque interface and ArrayDeque, written by Josh Bloch and Doug Lea: a resizable circular array, no locks, no nulls. Its Javadoc says it is "likely to be faster than Stack when used as a stack", and Stack's own Javadoc tells you to prefer Deque.

the problem it solvedA fast, unsynchronized stack and queue in one class, without Vector's locking and LIFO-breaking methods.

its jobs today

The default stack (push/pop/peek) and queue (offer/poll) in modern Java code — and the one interviewers expect.
Explicit stacks for iterative DFS and for replacing deep recursion; deques for sliding-window problems.

the weight it carries

Illustrative, using JDK 17's growth rule (17 slots at first, about doubling while small, then +50% each time): 10⁶ pushes cause 26 resizes. Each copies the old array (2.48·10⁶ elements in total) and, because push fills from the front, slides that block to the far end too — about 4.95·10⁶ element moves, roughly 5 per push, so push stays O(1) amortized. A LinkedList would allocate 10⁶ node objects instead.

without it

You'd choose between a locked legacy Stack that iterates bottom → top and a LinkedList that allocates an object per push.

when · why · how

when: Any time you need a stack or a queue in Java — unless you must store null or share it between threads.
why: push, pop and peek are amortized O(1) with no lock and compact array memory; Stack pays for synchronization and exposes non-stack methods.
how: Deque<Integer> st = new ArrayDeque<>(); then push/pop/peek. For-each goes top → bottom; descendingIterator() goes bottom → top.

02 · plain english

The idea in 30 seconds

A stack only lets you touch the top: push adds there, pop removes from there, peek looks there. All O(1).

Use it whenever the most recent unfinished thing must be handled first: an open bracket, a pending number, a function call.

A monotonic stack keeps its items sorted, so each new item instantly answers "who was waiting for something bigger (or smaller) than me?"

picture this

Ctrl+Z in your editor. Every change is pushed onto an undo stack; Ctrl+Z pops the most recent one. To undo the change you made three steps ago, you must first undo the two that came after it.

03 · remember

What you must know

LIFO — last in, first out. push, pop, peek, isEmpty are all O(1); searching inside is O(n) and almost never needed.
In Java, use Deque<Integer> stack = new ArrayDeque<>(). Not the legacy Stack class (it extends Vector, is synchronized, and iterates bottom → top).
An array-backed stack is just an array plus a size index. Doubling the array when full keeps push O(1) amortized.
Matching / nesting problems (brackets, tags, k[...], paths with ..): push when something opens, pop when it closes.
Monotonic stack: before pushing x, pop everything that x "beats". Each popped item has just found its answer — x.
Each element is pushed once and popped at most once, so a while inside a for is still O(n) in total.
Store indices, not values, on a monotonic stack — you can always read the value, and you'll need the index for distances and widths.
Recursion is a stack (the call stack). Any recursive DFS can be rewritten with an explicit Deque when depth might overflow.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Push, pop, peek — and what happens in memory

Top: the backing array and the `size` index. Bottom: the stack you reason about. Watch the array double when it fills up.

loading simulation…

javajava.util.*

1class ArrayStack {2    private int[] data = new int[2]; // starts tiny so you can watch it grow3    private int size = 0;            // also the index of the next free slot4 5    void push(int x) {6        if (size == data.length) data = Arrays.copyOf(data, size * 2);7        data[size++] = x;8    }9 10    int pop() {11        if (size == 0) throw new RuntimeException("stack is empty");12        return data[--size];13    }14 15    int peek() {16        if (size == 0) throw new RuntimeException("stack is empty");17        return data[size - 1];18    }19 20    boolean isEmpty() { return size == 0; }21    int size() { return size; }22}

sim

Matching brackets with a stack

Every closer must match the most recent unmatched opener — exactly what the top of the stack holds.

loading simulation…

javajava.util.*

1class Solution {2    public boolean isValid(String s) {3        Deque<Character> stack = new ArrayDeque<>();4        for (char c : s.toCharArray()) {5            if (c == '(' || c == '[' || c == '{') {6                stack.push(c);7            } else {8                if (stack.isEmpty()) return false;9                char open = stack.pop();10                if (!matches(open, c)) return false;11            }12        }13        return stack.isEmpty();14    }15 16    private boolean matches(char open, char close) {17        return (open == '(' && close == ')')18            || (open == '[' && close == ']')19            || (open == '{' && close == '}');20    }21}

sim

Monotonic stack — next greater element

Amber bars are still waiting. A taller bar arrives and settles every shorter bar on top of the stack at once.

loading simulation…

javajava.util.*

1class NextGreater {2    /** ans[i] = first value to the right of i that is bigger than nums[i], or -1. */3    static int[] nextGreater(int[] nums) {4        int n = nums.length;5        int[] ans = new int[n];6        Arrays.fill(ans, -1);7        Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting; values decrease bottom -> top8        for (int i = 0; i < n; i++) {9            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {10                ans[stack.pop()] = nums[i]; // nums[i] is the answer for the popped index11            }12            stack.push(i);13        }14        return ans; // whoever is still waiting keeps -115    }16}

sim

Largest rectangle in a histogram

An increasing stack of bars. When a shorter bar arrives, the taller bars can't stretch further — measure their rectangles now.

loading simulation…

javajava.util.*

1class Solution {2    public int largestRectangleArea(int[] heights) {3        int n = heights.length, best = 0;4        Deque<Integer> stack = new ArrayDeque<>(); // indices; heights increase bottom -> top5        for (int i = 0; i <= n; i++) {6            int h = (i == n) ? 0 : heights[i]; // a final 0 flushes every bar out7            while (!stack.isEmpty() && heights[stack.peek()] >= h) {8                int height = heights[stack.pop()];9                int left = stack.isEmpty() ? -1 : stack.peek();10                int width = i - left - 1;11                best = Math.max(best, height * width);12            }13            stack.push(i);14        }15        return best;16    }17}

05 · cost

Time & space, explained

Stack operations
	ArrayDeque	Raw array + size	Linked nodes	why
push(x)	O(1) amortized	O(1) amortized	O(1)	Write at the top. When an array is full it is copied into a bigger one — rare enough that the average stays O(1).
pop()	O(1)	O(1)	O(1)	Remove the top: move an index (array) or one reference (linked). Nothing shifts.
peek()	O(1)	O(1)	O(1)	Read the top without changing anything.
isEmpty() / size()	O(1)	O(1)	O(1)	Both keep a counter (or head/tail indices).
contains(x) / search	O(n)	O(n)	O(n)	Nothing is indexed by value — you'd have to walk the whole stack.
Memory for n items	O(n)	O(n)	O(n)	Same Big-O, but linked nodes pay an object header + a reference per item; arrays are compact and cache-friendly.

Monotonic stack vs brute force
	Brute force	Monotonic stack	Stack space	why
Next greater element (each index)	O(n²)	O(n)	O(n)	Brute force scans right from every index. The stack pushes each index once and pops it at most once.
Daily temperatures	O(n²)	O(n)	O(n)	Same pattern: a day leaves the stack the moment its warmer day arrives.
Largest rectangle in histogram	O(n²)	O(n)	O(n)	Brute force tries every range. The stack finds each bar's nearest shorter neighbours in one pass.
Worst case for stack size	—	—	n	A strictly decreasing input (for next greater) never pops, so all n indices wait on the stack.

06 · java

Raw vs Collections Framework

A stack from scratch vs ArrayDeque

javaarray + size (what's inside)java.util.*

1class ArrayStack {2    private int[] data = new int[2]; // starts tiny so you can watch it grow3    private int size = 0;            // also the index of the next free slot4 5    void push(int x) {6        if (size == data.length) data = Arrays.copyOf(data, size * 2);7        data[size++] = x;8    }9 10    int pop() {11        if (size == 0) throw new RuntimeException("stack is empty");12        return data[--size];13    }14 15    int peek() {16        if (size == 0) throw new RuntimeException("stack is empty");17        return data[size - 1];18    }19 20    boolean isEmpty() { return size == 0; }21    int size() { return size; }22}

javaArrayDeque as a stackjava.util.*

1class DequeAsStack {2    static List<Integer> demo() {3        Deque<Integer> stack = new ArrayDeque<>(); // the go-to stack in modern Java4        stack.push(1);                  // [1]5        stack.push(2);                  // [2, 1]  <- push adds at the head (the top)6        stack.push(3);                  // [3, 2, 1]7        int top = stack.peek();         // 3, not removed8        int popped = stack.pop();       // 3, removed9        Integer none = new ArrayDeque<Integer>().peek(); // peek on empty -> null (pop would throw)10        List<Integer> out = new ArrayList<>(List.of(top, popped, stack.size()));11        out.add(none == null ? -1 : none);12        out.addAll(stack);              // iterates top -> bottom: 2, 113        return out;14    }15}

size is both the number of items and the index of the next free slot — so data[size++] = x pushes and data[--size] pops.
Doubling when full means n pushes cost at most about 2n copies in total: O(1) amortized per push.
ArrayDeque.push = addFirst, pop = removeFirst, peek = peekFirst. The head of the deque is the top of the stack.
pop() on an empty ArrayDeque throws NoSuchElementException; peek() and poll() return null instead.
ArrayDeque does not allow null elements (push(null) throws NullPointerException).

Linked stack, and why not java.util.Stack

javalinked nodesjava.util.*

1class LinkedStack {2    private static class Node {3        final int value;4        final Node next; // the node *below* this one5        Node(int value, Node next) { this.value = value; this.next = next; }6    }7 8    private Node top = null;9    private int size = 0;10 11    void push(int x) { top = new Node(x, top); size++; } // new node points at the old top12 13    int pop() {14        if (top == null) throw new RuntimeException("stack is empty");15        int value = top.value;16        top = top.next; // the old top becomes garbage17        size--;18        return value;19    }20 21    int peek() {22        if (top == null) throw new RuntimeException("stack is empty");23        return top.value;24    }25 26    boolean isEmpty() { return top == null; }27    int size() { return size; }28}

javalegacy Stack vs ArrayDequejava.util.*

1class LegacyVsDeque {2    static String compare() {3        Stack<Integer> legacy = new Stack<>();   // extends Vector: synchronized, allows get(i)4        Deque<Integer> modern = new ArrayDeque<>();5        for (int x : new int[] {1, 2, 3}) {6            legacy.push(x);7            modern.push(x);8        }9        // Same pops, different iteration order!10        return "Stack iterates " + legacy + ", ArrayDeque iterates " + modern;11    }12}

A linked stack pushes by making a new node point at the old top. No resizing ever — but one object allocation per push.
Stack extends Vector: every method is synchronized (lock overhead you don't need) and it exposes get(i)/add(i, x), which break LIFO.
Stack iterates bottom → top; ArrayDeque iterates top → bottom. Printing or looping over them gives opposite orders.
The Stack Javadoc itself says to prefer Deque implementations. ArrayDeque is documented as "likely to be faster than Stack when used as a stack".

Next greater element: brute force vs monotonic stack

javabrute force O(n²)java.util.*

1class BruteNextGreater {2    /** For each index, scan right until something bigger appears. */3    static int[] nextGreater(int[] nums) {4        int[] ans = new int[nums.length];5        for (int i = 0; i < nums.length; i++) {6            ans[i] = -1;7            for (int j = i + 1; j < nums.length; j++) {8                if (nums[j] > nums[i]) { ans[i] = nums[j]; break; }9            }10        }11        return ans;12    }13}

javamonotonic stack O(n)java.util.*

1class NextGreater {2    /** ans[i] = first value to the right of i that is bigger than nums[i], or -1. */3    static int[] nextGreater(int[] nums) {4        int n = nums.length;5        int[] ans = new int[n];6        Arrays.fill(ans, -1);7        Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting; values decrease bottom -> top8        for (int i = 0; i < n; i++) {9            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {10                ans[stack.pop()] = nums[i]; // nums[i] is the answer for the popped index11            }12            stack.push(i);13        }14        return ans; // whoever is still waiting keeps -115    }16}

The stack holds indices still waiting for their answer. Their values decrease from bottom to top.
"Next" questions are answered when an item is popped (the newcomer is its answer).
Flip < to > for next smaller. Use <= instead of < if equal values should also count as "not bigger".

Previous smaller element: answer on push

javaprevious smaller indexjava.util.*

1class PreviousSmaller {2    /** ans[i] = index of the nearest element to the LEFT that is strictly smaller, or -1. */3    static int[] previousSmallerIndex(int[] nums) {4        int[] ans = new int[nums.length];5        Deque<Integer> stack = new ArrayDeque<>(); // values increase bottom -> top6        for (int i = 0; i < nums.length; i++) {7            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) stack.pop();8            ans[i] = stack.isEmpty() ? -1 : stack.peek(); // survivor on top is the answer9            stack.push(i);10        }11        return ans;12    }13}

"Previous" questions are answered when an item is pushed: after popping everything it beats, the survivor on top is its answer.
Running this left-to-right and right-to-left gives each bar's nearest shorter neighbours — the heart of Largest Rectangle.

Java API you will actually use
call	does	cost
`Deque<Integer> st = new ArrayDeque<>()`	Create an empty stack (resizable circular array)	O(1)
`st.push(x)`	Put x on top (same as addFirst)	O(1) amortized
`st.pop()`	Remove and return the top; throws NoSuchElementException if empty	O(1)
`st.peek()`	Return the top without removing it; null if empty	O(1)
`st.poll()`	Like pop(), but returns null when empty	O(1)
`st.isEmpty() / st.size()`	Check before popping / count items	O(1)
`st.peekLast() / st.pollLast()`	Look at / remove the bottom item	O(1)
`for (int x : st)`	Iterate top → bottom (use descendingIterator() for bottom → top)	O(n)
`int[] st = new int[n]; int top = 0;`	Hand-rolled int stack: st[top++] = x, st[--top]	O(1), no boxing

A stack in an interview (any type)

→ Deque<T> st = new ArrayDeque<>()

Fast, idiomatic, and what interviewers expect in modern Java.

A hot loop over ints with a known max size

→ int[] + top index

No Integer boxing, no resizing — fastest possible.

Read the stack bottom → top at the end (e.g. build a path)

→ ArrayDeque with pollLast() / descendingIterator()

Both ends are O(1) in a deque.

Store null as a real value

→ ArrayList<T> (add / remove(size − 1))

ArrayDeque rejects null; an ArrayList's end works as a stack.

A stack shared by several threads

→ ConcurrentLinkedDeque or LinkedBlockingDeque

Built for concurrency — still don't use legacy Stack.

07 · recognise

Spot the pattern

Brackets, tags or anything that opens and closes and can nest

Push openers; a closer must match the top

"Next greater / smaller", "how many days until warmer", "nearest taller to the left"

Monotonic stack of indices

Largest rectangle, maximal area under bars, "span" of a value

Increasing monotonic stack; measure when a bar is popped

Postfix / prefix expression, calculator, "evaluate"

Operand stack (plus an operator stack for infix)

Nested encoding like 3[a2[c]], or a path with ..

Stack of saved contexts — push on open, pop and combine on close

"Undo", "go back", "most recent first"

A plain stack of states

Things meet or cancel out: colliding asteroids, a backspace # erasing the last letter

Stack of survivors — the newcomer fights the most recent one first

"Longest valid / balanced substring"

Stack of indices with a base index at the bottom; measure i − top

Recursion might be too deep, or you're asked to do it iteratively

Explicit stack replaces the call stack

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Calling pop() or peek() on an empty stack. Check isEmpty() first — a lone ) or ] is the classic test case.
Using legacy java.util.Stack and then iterating it expecting top-first order. It iterates bottom → top.
Comparing two Integers with == (e.g. stack.peek() == mins.peek()). Outside −128..127 that compares references. Unbox to int or use .equals.
Popping operands in the wrong order: for a b - the first pop is b. Getting it backwards breaks - and /.
Pushing values when you need distances or widths — push indices instead.
Forgetting the leftovers: items still on the stack at the end need a default answer (−1 / 0) or a final flush (the height-0 sentinel).
Mixing up < and <= in the pop condition. With duplicates, one of them is wrong for your problem — test [2, 2, 2].
ArrayDeque refuses null. Pushing a null (e.g. from a map lookup) throws NullPointerException.
Turning a stack back into an array by iterating it: ArrayDeque iterates top → bottom, so the answer comes out reversed. Fill the array from the back, or use pollLast().

tricks

Say the invariant out loud: "the stack holds indices still waiting, and their values decrease from bottom to top."
Before coding a monotonic stack, answer two questions: what waits on the stack? and what makes it leave? Leaving = getting an answer.
Defend O(n) with one sentence: "each index is pushed once and popped at most once, so the inner while runs at most n times in total."
"Next …" questions are answered on pop. "Previous …" questions are answered on push (the survivor on top).
Dry-run on paper with the stack drawn sideways: [ 7 5 3 ←top. It makes the pops obvious.
Edge cases to test: empty input, one element, all equal, strictly increasing, strictly decreasing.

09 · why & how

Questions you might be too shy to ask

Why ArrayDeque and not the Stack class I learned in school?

Stack is a 1990s class that extends Vector. Every call takes a lock (synchronized), it lets you break LIFO with get(i) and add(i, x), and it iterates bottom → top. The Java docs themselves recommend Deque. ArrayDeque is unsynchronized, compact and faster. Interviewers notice this choice.

I pushed 1, 2, 3 and printing the stack shows [3, 2, 1]. Is it broken?

No, it's working perfectly. ArrayDeque.push adds at the front, and printing or a for-each goes front to back. So you see the top first: [3, 2, 1], and peek() gives 3. Need bottom → top instead (e.g. to build a path)? Use descendingIterator() or pollLast().

Can I use an ArrayList as a stack?

Yes. add(x) pushes at the end and remove(list.size() - 1) pops — both O(1) (amortized for add). Never use remove(0): that shifts every element, O(n). ArrayDeque is still the cleaner default.

Array-backed or linked stack — which is better?

Both give O(1) push/pop. Arrays win in practice: items sit next to each other in memory (cache-friendly) and there's no object per item. A linked stack never needs a resize copy, which matters only for hard real-time guarantees. ArrayDeque is array-backed.

How do I tell if a problem wants a stack or a queue?

Ask one question: who must be handled first — the newest waiting item or the oldest? Newest first (the last open bracket, the last undo step) → stack. Oldest first (print jobs, BFS level by level) → queue, the next chapter. Example: in "([)]" the ) is checked against the newest opener [ — so it's a stack problem.

What does "the call stack" have to do with this?

When a method calls another, the JVM pushes a frame (its locals and return point) on the call stack; returning pops it. That's why deep recursion throws StackOverflowError. Any recursion can be rewritten with your own Deque — see Decode String below, and the explicit-stack approach to Generate Parentheses in the Backtracking chapter.

Recursion or my own stack — which should I write in the interview?

Recursion is shorter, and fine when the depth stays small. In Decode String the input is at most 30 characters, so nesting is tiny. If depth can get large (very roughly 10⁴ calls or more — the real limit depends on the frame size and the JVM's stack setting), the call stack may overflow. Your own Deque keeps its items on the heap, which is far bigger. A safe line to say: "I'll write it recursively, and switch to an explicit stack if the depth can get large."

There's a while loop inside a for loop. How is that O(n) and not O(n²)?

Count work per element, not per loop. Every index is pushed exactly once and popped at most once. All the inner while iterations together can't pop more than n items. So the total is at most 2n operations — O(n). This is called an amortized argument.

How do I know if the stack should be increasing or decreasing?

Ask what you're looking for. Next greater → pop smaller items when a bigger one comes → the stack stays decreasing. Next smaller (or largest rectangle) → pop bigger items → the stack stays increasing. Then write the pop condition and check it with [2, 2, 2].

< or <= in the pop condition — how do I decide?

Read the problem's word "greater" carefully. Next strictly greater → pop while top < x; an equal value is not an answer, so it keeps waiting. Try [2, 2, 3]: with <, both 2s wait and 3 answers both — correct. With <=, the second 2 pops the first and becomes its "answer" — wrong. If the problem says "greater or equal", then <= is right. Dhyan do: one character decides it, so always test a duplicate.

Should I push values or indices?

Indices, almost always. From an index you get the value (nums[i]) and the position, which you need for "days to wait" (i − j) or a rectangle's width. Pushing values throws the position away.

Largest Rectangle pops equal bars too (>=). Doesn't that measure a wrong width?

The first of two equal bars does get measured too narrow — but the best answer is never missed. With [3, 3]: at i = 1 the first 3 pops with width 1 (area 3). The second 3 waits till the end and pops with width 2 (area 6). In the best rectangle, the rightmost bar of the lowest height always gets the full width, so the max is still correct.

Car Fleet: why sort by position if I only compare times?

Because a car can only be blocked by the cars in front of it on the road. Sorting front-first lines cars up in road order. Then "my time ≤ the fleet ahead's time" really means "I catch them at or before the target". Without the sort, you'd compare a car with someone who is behind it — and that car can never block it.

I understood the monotonic stack solution, but I go blank when I write it. What now?

Normal hai — reading and writing are different skills. Close the solution and write the template from memory: a for over i, a while that pops and answers, then push(i). Dry-run it on [73, 74, 75, 71, 69, 72] with the stack drawn on paper. Then solve Daily Temperatures, Next Greater Element I and Largest Rectangle in that order without peeking. Write it once more after 2–3 days — the second time, it sticks.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#20
Valid Parenthesesmust-do
EasyIntuitWalmartBloombergLinkedInNVIDIA+1
#155
Min Stackmust-do
MediumBloombergOracleAmazonMicrosoftGoogle+1
#150
Evaluate Reverse Polish Notationmust-do
MediumLinkedInAmazonGoogleMeta
#739
Daily Temperaturesmust-do
MediumByteDance / TikTokAmazonBloombergMicrosoftGoogle+1
#496
Next Greater Element I
EasyBloombergAmazonMicrosoftGoogle
#84
Largest Rectangle in Histogrammust-do
HardFlipkartAmazonGoogleMicrosoftBloomberg+1
#853
Car Fleet
MediumGoogleAmazon
#394
Decode Stringmust-do
MediumBloombergByteDance / TikTokGoogleMetaAmazon+1
#71
Simplify Path
MediumMetaMicrosoftAmazonGoogle
#32
Longest Valid Parentheses
HardMetaAmazonMicrosoftGoogle
#735
Asteroid Collisionmust-do
MediumPayPalOracleAmazonUberMicrosoft+1
#844
Backspace String Compare
EasyGoogleMicrosoftAmazonMeta

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#22
Generate Parentheses
Mediumin Backtracking
Its explicit-Deque approach shows the stack that recursion hides; the open/close rules are bracket matching run in reverse.
#232
Implement Queue using Stacks
Easyin Queues
Two stacks make a queue with amortized O(1) per operation — the same push-once, pop-once counting as a monotonic stack.
#239
Sliding Window Maximum
Hardin Queues
The monotonic idea on a deque: drop dominated values from the back, expired ones from the front.

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
A stack touches only its top: push, pop, peek — all O(1). Last in, first out: the most recent unfinished thing is handled first.
use it when
Brackets and tags that nest, undo, postfix, k[...], .. in paths, things that collide or cancel — wherever the newest item settles first.
use it when
"Next greater / smaller", "days until warmer", the widest rectangle → a monotonic stack of indices.
template
while (!st.isEmpty() && a[st.peek()] < a[i]) ans[st.pop()] = a[i]; st.push(i); — each pop gets its answer from the newcomer.
cost
Each index is pushed once and popped at most once → O(n) time, even with a while inside the for. Stack space: O(n) worst case.
trap
pop() on an empty ArrayDeque throws; peek() returns null. Check isEmpty() first — and check the stack is empty at the end.
trap
stack.peek() == mins.peek() on two Integers compares references: fine up to 127, wrong for 1000. Unbox to int first.
trap
Postfix: the first pop() is the right operand. For a b -, pop b, then a, push a − b.
pro tip
Use Deque<Integer> st = new ArrayDeque<>(), not legacy Stack. Push indices, not values, so you can measure distances and widths.

12 · recall

Flip, remember, repeat

card 1 / 15

recall

Which stack operations are O(1), and what is slow?

tap or Space to flip ↻

Question 1: Which stack operations are O(1), and what is slow?

13 · check yourself

Quick quiz

You push 1, 2, 3, then pop once, then push 4. What does peek() return?
Why prefer ArrayDeque over java.util.Stack?
A monotonic stack algorithm has a while loop inside a for loop over n items. Its time is…
For "next greater element", the stack's values from bottom to top are…
Evaluating RPN ["8", "2", "-"]: the first pop gives…
Valid Parentheses: the string is "(()". What tells you it's invalid?
In Largest Rectangle in Histogram, bar 4 is popped while i = 7 and the new top is index 2. The rectangle's width is…
Asteroid Collision on [3, 5, −6, 2, −1, 4]. What is left?

0/0 correct · 8 left

14 · learn more