Learning/Stack

Stack

7 questions. Two distinct families share one data structure, and telling them apart is the whole skill.

The one idea

A stack is right whenever the most recently seen unresolved item is the one you must resolve first.

That single sentence covers both families in this section:

Family A — matching and evaluation. Brackets, expressions, undo. When a ) arrives, it must match the most recent unclosed (. "Most recent" is a stack.

Family B — monotonic stacks. "Next greater element", spans, histograms. Here the stack holds items still waiting for an answer, kept in sorted order — and an arriving element resolves several of them at once.

Family B is the harder and more transferable idea. Four of the seven questions use it.

The monotonic stack, in one picture

You're at day 5 (72°) in Daily Temperatures. Days 4 (69°) and 3 (71°) are both still waiting for a warmer day — and 72° answers both at once.

Better still: once a warmer day exists to the right of a cooler one, that cooler day is permanently irrelevant to everything further right. Anything that would warm the later day also warms it.

So keep a stack of items still waiting, maintained in sorted order. When an element arrives that resolves the ones on top, pop them all and record their answers.

Stack keeps valuesPopping triggered byAnswers
DecreasingA larger element arriving"Next greater element"
IncreasingA smaller element arriving"Next smaller", histogram spans

Choosing the orientation: ask "what event finally lets me answer for something I already passed?" That event is the pop trigger, and it fixes the direction.

Why it's O(n), not O(n²)

The while nested inside the for looks quadratic. It isn't:

Each element is pushed exactly once and popped at most once. So across the entire outer loop, the inner while body executes at most n times in total.

Some single iterations pop fifty items; then fifty later iterations pop nothing. Bound the total work, not the worst case of one step. This is the same aggregate argument as the sliding window and Longest Consecutive Sequence — and interviewers ask for it by name in this section.

Easy Valid Parentheses LC 20 13 min Medium Min Stack LC 155 16 min Medium Evaluate Reverse Polish Notation LC 150 14 min Medium Generate Parentheses LC 22 14 min Medium Daily Temperatures LC 739 17 min Medium Car Fleet LC 853 17 min Hard Largest Rectangle in Histogram LC 84 20 min

Use ArrayDeque, not Stack

Java
Deque<Integer> stack = new ArrayDeque<>();
stack.push(x);      // addFirst
stack.pop();        // removeFirst — throws if empty
stack.peek();       // peekFirst — null if empty
stack.isEmpty();

java.util.Stack is a legacy synchronized Vector — you pay for thread-safety you aren't using on every call, and it iterates bottom-to-top, which is the opposite of what you expect. Interviewers notice the choice. See 02 — Java Collections Toolkit §5.

Prerequisites from Part 1

09 Stack & Monotonic Stack the pattern summary this section instantiates02 Java Collections Toolkit §5 — the Deque API, including the throws-vs-null method families01 Complexity & Problem Triage the amortized argument above15 Backtracking needed for Q4, which is filed here but is really a backtracking problem

How to work this section

  1. Read §1 and §2 only, then attempt cold with a timer — 20 min Easy, 35 Medium, 45 Hard.
  2. After the attempt, read §3 and §4 and diff against your reasoning.
  3. Use the counter-questions in §3 as a quiz — for each approach, cover the answers and defend it yourself.
  4. Read §7 last: the modified-constraint variants.

For Q5 and Q7 especially: rehearse the amortized O(n) argument aloud. It is asked essentially every time, and "each element is pushed once and popped at most once" is the whole answer.

What to carry forward