Skip to content

Topic 5 of 20

Stack & Monotonic Stack

Last-in-first-out processing for parsing, undo-style logic and 'next greater' questions.

25 problems7 Easy14 Medium4 Hard

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. 1

    The canonical stack question; often the first problem in a phone screen.

    Matching / ParsingReported at: AmazonMetaMicrosoft+16
  2. 2

    Straightforward operation simulation to get comfortable with push and pop.

    Stack SimulationReported at: Uber
  3. 3

    Stack simulation, with a two-pointer O(1)-space follow-up.

    Stack SimulationReported at: GoogleAppleIBM+3
  4. 4

    Using the stack as a 'last kept character' buffer.

    Stack SimulationReported at: MetaAmazon
  5. 5

    Amortised O(1) with two stacks; a common design warm-up.

    Two StacksReported at: AmazonMicrosoftGoogle+1
  6. 6

    The reverse exercise, to cement how both structures behave.

    Queue SimulationReported at: Amazon
  7. 7

    The simplest monotonic-stack question; learn the template here.

  8. 8
    Min StackMedium

    Keeping auxiliary state per element is a reusable design trick.

    Min/Aux StackReported at: AmazonMicrosoftMeta+5
  9. 9

    Stack-based expression evaluation, the basis of calculators.

    Expression EvaluationReported at: GoogleAmazonMeta+3
  10. 10

    Next-greater distance; the most-asked monotonic-stack Medium.

    Monotonic StackReported at: MetaAmazonMicrosoft+2
  11. 11
    Car FleetMedium

    Sorting by position then stacking arrival times; a clever modelling problem.

  12. 12

    Previous-greater spans in a streaming (online) setting.

    Monotonic StackReported at: AmazonBloombergAdobe
  13. 13

    Handles a circular array by iterating twice.

  14. 14

    Collision rules make you think about exactly when to pop.

    Stack SimulationReported at: AmazonMetaMicrosoft+4
  15. 15

    Nested brackets handled with a stack of (string, count) frames.

    Nested ParsingReported at: GoogleMicrosoftAmazon+11
  16. 16

    Path canonicalisation, a practical parsing task.

    Stack SimulationReported at: MetaAmazonGoogle+1
  17. 17

    Tracking indices of unmatched brackets; a frequent Meta question.

    Matching / ParsingReported at: MetaAmazonMicrosoft+4
  18. 18

    A greedy monotonic stack that builds the smallest number.

    Monotonic Stack (Greedy)Reported at: AmazonMicrosoftGoogle+4
  19. 19

    Greedy monotonic stack with 'last occurrence' look-ahead.

    Monotonic Stack (Greedy)Reported at: AppleAmazonMeta+1
  20. 20

    Scans from the right while tracking a candidate value; a tricky monotonic stack.

    Monotonic StackReported at: Amazon
  21. 21

    Counts each element's contribution using previous/next smaller elements.

  22. 22

    The defining Hard monotonic-stack problem.

    Monotonic StackReported at: AmazonMicrosoftMeta+5
  23. 23

    Reduces a 2D grid to repeated histogram problems.

    Monotonic Stack per RowReported at: GoogleAmazonApple
  24. 24

    Signs and nested parentheses with a stack; asked at Google and Meta.

    Expression EvaluationReported at: GoogleMetaAmazon+6
  25. 25

    Uses stack indices to measure valid spans, with a DP alternative.

    Matching / ParsingReported at: AmazonMetaMicrosoft+4