Topic 5 of 20
Last-in-first-out processing for parsing, undo-style logic and 'next greater' questions.
A stack gives you last-in-first-out (LIFO) access in O(1). It is the natural structure whenever the most recent unfinished thing must be dealt with first: matching brackets, undoing operations, evaluating nested expressions, or simulating recursion by hand.
The most important interview pattern here is the monotonic stack: a stack whose values are kept strictly increasing (or decreasing). When a new element breaks the order, you pop, and every pop answers a question such as "what is the next greater element to my right?" or "how far can this bar extend?". Each element is pushed and popped once, so these solutions run in O(n) even though they look nested.
Learn to recognise the trigger phrases: next greater/smaller, previous greater/smaller, span, histogram, remove digits to make the smallest number. Once you see them, the monotonic stack is almost always the intended solution.
The canonical stack question; often the first problem in a phone screen.
Straightforward operation simulation to get comfortable with push and pop.
Stack simulation, with a two-pointer O(1)-space follow-up.
Using the stack as a 'last kept character' buffer.
Amortised O(1) with two stacks; a common design warm-up.
The reverse exercise, to cement how both structures behave.
The simplest monotonic-stack question; learn the template here.
Keeping auxiliary state per element is a reusable design trick.
Stack-based expression evaluation, the basis of calculators.
Next-greater distance; the most-asked monotonic-stack Medium.
Sorting by position then stacking arrival times; a clever modelling problem.
Previous-greater spans in a streaming (online) setting.
Collision rules make you think about exactly when to pop.
Nested brackets handled with a stack of (string, count) frames.
Path canonicalisation, a practical parsing task.
Tracking indices of unmatched brackets; a frequent Meta question.
A greedy monotonic stack that builds the smallest number.
Greedy monotonic stack with 'last occurrence' look-ahead.
Scans from the right while tracking a candidate value; a tricky monotonic stack.
Counts each element's contribution using previous/next smaller elements.
The defining Hard monotonic-stack problem.
Reduces a 2D grid to repeated histogram problems.
Signs and nested parentheses with a stack; asked at Google and Meta.
Uses stack indices to measure valid spans, with a DP alternative.