Topic 5 of 20
Stack & Monotonic Stack
Last-in-first-out processing for parsing, undo-style logic and 'next greater' questions.
The concept
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.
Patterns you will learn
Problems, in order
- 1
The canonical stack question; often the first problem in a phone screen.
Matching / ParsingReported at: AmazonMetaMicrosoft+16 - 2Baseball GameEasy
Straightforward operation simulation to get comfortable with push and pop.
Stack SimulationReported at: Uber - 3
Stack simulation, with a two-pointer O(1)-space follow-up.
Stack SimulationReported at: GoogleAppleIBM+3 - 4
Using the stack as a 'last kept character' buffer.
Stack SimulationReported at: MetaAmazon - 5
Amortised O(1) with two stacks; a common design warm-up.
Two StacksReported at: AmazonMicrosoftGoogle+1 - 6
The reverse exercise, to cement how both structures behave.
Queue SimulationReported at: Amazon - 7
The simplest monotonic-stack question; learn the template here.
- 8Min StackMedium
Keeping auxiliary state per element is a reusable design trick.
Min/Aux StackReported at: AmazonMicrosoftMeta+5 - 9
Stack-based expression evaluation, the basis of calculators.
Expression EvaluationReported at: GoogleAmazonMeta+3 - 10Daily TemperaturesMedium
Next-greater distance; the most-asked monotonic-stack Medium.
Monotonic StackReported at: MetaAmazonMicrosoft+2 - 11Car FleetMedium
Sorting by position then stacking arrival times; a clever modelling problem.
- 12Online Stock SpanMedium
Previous-greater spans in a streaming (online) setting.
Monotonic StackReported at: AmazonBloombergAdobe - 13
- 14Asteroid CollisionMedium
Collision rules make you think about exactly when to pop.
Stack SimulationReported at: AmazonMetaMicrosoft+4 - 15Decode StringMedium
Nested brackets handled with a stack of (string, count) frames.
Nested ParsingReported at: GoogleMicrosoftAmazon+11 - 16Simplify PathMedium
Path canonicalisation, a practical parsing task.
Stack SimulationReported at: MetaAmazonGoogle+1 - 17
Tracking indices of unmatched brackets; a frequent Meta question.
Matching / ParsingReported at: MetaAmazonMicrosoft+4 - 18Remove K DigitsMedium
A greedy monotonic stack that builds the smallest number.
Monotonic Stack (Greedy)Reported at: AmazonMicrosoftGoogle+4 - 19Remove Duplicate LettersMedium
Greedy monotonic stack with 'last occurrence' look-ahead.
Monotonic Stack (Greedy)Reported at: AppleAmazonMeta+1 - 20132 PatternMedium
Scans from the right while tracking a candidate value; a tricky monotonic stack.
Monotonic StackReported at: Amazon - 21Sum of Subarray MinimumsMedium
Counts each element's contribution using previous/next smaller elements.
- 22
The defining Hard monotonic-stack problem.
Monotonic StackReported at: AmazonMicrosoftMeta+5 - 23
Reduces a 2D grid to repeated histogram problems.
Monotonic Stack per RowReported at: GoogleAmazonApple - 24Basic CalculatorHard
Signs and nested parentheses with a stack; asked at Google and Meta.
Expression EvaluationReported at: GoogleMetaAmazon+6 - 25
Uses stack indices to measure valid spans, with a DP alternative.
Matching / ParsingReported at: AmazonMetaMicrosoft+4