Command Palette

Search for a command to run...

Hectal

Module 9

Stack and Monotonic Stack

Last in, first out: match brackets, undo, evaluate expressions, and find the next greater element for every item in one pass.

Intermediate 3 lessons 8 problems ~40 min of lessons
Stack for Matching and UndoMonotonic Stack

A stack only lets you touch its top. That restriction is exactly what nested structures need: the most recently opened bracket must close first, the most recent action is undone first, and the innermost expression is evaluated first.

The second half of the module covers the monotonic stack, a stack kept in sorted order. It answers "what is the next greater (or smaller) element?" for every position in O(n), and it's the key to problems like Daily Temperatures and Largest Rectangle in Histogram.

Best after: Arrays

Part 1

Learn the ideas

  1. 9.1How a Stack WorksPush onto the top, pop from the top, peek at the top. All O(1). Use `ArrayDeque`, not the old `Stack` class.10 min
  2. 9.2Matching and NestingPush every opener; when a closer arrives it must match the opener on top. Anything left over, or a mismatch, means invalid.12 min
  3. 9.3The Monotonic StackKeep indexes on a stack whose values decrease from bottom to top. Each new element pops every smaller one, and is their "next greater element".16 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 9.1Valid ParenthesesEasyStack for Matching and Undo

    The canonical stack problem: the most recent opener must close first.

  2. 9.2Min StackMediumCombine Structures to Design

    Store extra state with each element (the minimum so far) so every query stays O(1).

  3. 9.3Evaluate Reverse Polish NotationMediumStack for Matching and Undo

    Postfix expressions need no brackets: push numbers, and each operator pops its two operands.

  4. 9.4Decode StringMediumStack for Matching and Undo

    Stacks of saved state: on '[' save what you've built and the repeat count; on ']' pop and combine.

  5. 9.5Daily TemperaturesMediumMonotonic Stack

    The monotonic stack with distances: each warmer day pops every cooler day waiting on the stack.

  6. 9.6Next Greater ElementEasyMonotonic Stack

    Compute next-greater answers for one array with a monotonic stack, then look them up for another with a hash map.

  7. 9.7Car FleetMediumMonotonic Stack

    Sort by position, then compare arrival times from the front: a car that would arrive sooner than the fleet ahead joins it.

  8. 9.8Largest Rectangle in HistogramHardMonotonic Stack

    For each bar, the widest rectangle at its height spans to the nearest shorter bar on each side, found with an increasing stack.