Overview

A stack only lets you touch its top: push adds, pop removes, peek looks. That restriction is exactly what you want whenever the most recent unfinished thing must be resolved first — an opening bracket waiting for its partner, an operator waiting for its operands, a function call waiting to return.

The most powerful stack trick is the monotonic stack: a stack kept in increasing or decreasing order by popping anything that breaks the order before pushing. Each pop is the moment an element meets its "next greater" (or smaller) neighbour. Because every element is pushed and popped at most once, problems that look O(n²) — daily temperatures, largest rectangle in a histogram — fall to O(n).

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
push / pop / peekO(1)
Monotonic stack over n elementsO(n) total — each element pushed and popped once

Patterns to recognise

Match and cancel

Use it for: Valid parentheses, asteroid collision, removing adjacent duplicates.

Push; when the new item cancels the top, pop instead.

Next greater / smaller

Use it for: Daily temperatures, stock span, next greater element.

Store indices; pop while the current value beats the top, answering each popped index.

Nested structure

Use it for: Decode string, basic calculator.

Push the current context when you enter a bracket; pop and combine when you leave it.

Code template

Daily temperatures — monotonic stack
def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []                       # indices; temperatures decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j        # i is j's next warmer day
        stack.append(i)
    return answer

Common mistakes

  • Popping or peeking an empty stack — check before you touch the top.
  • Storing values when you later need positions; push indices and look values up.
  • Strict (<) vs non-strict (<=) comparisons change how duplicates are handled.

Quick check

Three questions on Stacks. Get all three right to earn +15 XP.

  1. A stack removes elements in which order?

  2. When checking balanced brackets, what do you do on reading a closing bracket?

  3. A monotonic stack solves "next greater element" for all n items in:

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Stacks?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor