Stacks and monotonic stacks

A stack is the simplest structure there is: push on top, pop from the top. It earns its own pattern because a surprising number of problems have last in, first out hiding inside them. The bracket opened most recently must close first. The operands read most recently are the ones an operator applies to. The function called most recently returns first.

Its sharper form, the monotonic stack, solves a family of problems that look like they need O(n²) on n elements. For every element, find the next element to its right that is bigger (or smaller). A monotonic stack answers all of them in one pass.

What makes this hard

• Use a plain stack when the most recent unfinished thing must be handled first: brackets, expressions, nested structures, undo.
• A monotonic stack holds items still waiting for an answer, kept in sorted order. A new item pops and answers everything it beats, then waits itself.
• Every item is pushed once and popped at most once, so the nested loop is O(n) in total.
• Store indexes, not values, when the answer is a distance or a width.

How to spot it

• Nesting or matching: brackets, tags, decoding 3[a2[c]], simplifying a file path.
• Expressions: reverse Polish notation, a basic calculator.
• “Next greater”, “next smaller”, “previous greater”, or anything phrased as “how long until” or “how far back”: daily temperatures, stock span, car fleet.
• Areas bounded by heights: largest rectangle in a histogram, maximal rectangle, trapping rain water (which also has a two pointers solution).

Watch it run

Daily temperatures: for each day, how many days until a warmer one? The stack holds days still waiting, and their temperatures decrease from bottom to top. A warm day pops every colder day on top, and each pop is an answer.

temperatures

730741752713694725766737

i

answer

········

stack bottom → top

0: 73°

1. answer = [0] * len(temperatures); stack = [] # days waiting
2. for i, temperature in enumerate(temperatures):
3. while stack and temperatures[stack[-1]] < temperature:
4. waiting_day = stack.pop()
5. answer[waiting_day] = i - waiting_day
6. stack.append(i)

Day 0 (73°) waits on the stack for a warmer day.

← BackStep →Play1 / 15

Look at day 5 (72°). It answers day 4 and day 3, but stops at day 2 (75°), which stays waiting. Day 6 (76°) then answers both day 5 and day 2. The order on the stack is what makes it fast. Once a day finds something it can’t beat, it can stop, because everything below is warmer still.

The template

Matching brackets with a plain stack, and next warmer day with a monotonic one:

JStacks.javaPyexample.pyC#Stacks.csGomain.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Stacks {
    static boolean isValid(String text) {
        // The most recent unclosed bracket must close first: last in, first out. The stack
        // holds the openers still waiting for their partner. ArrayDeque, not the legacy Stack
        // class, which is synchronized and extends Vector.
        Deque<Character> stack = new ArrayDeque<>();
        for (char bracket : text.toCharArray()) {
            switch (bracket) {
                case '(', '[', '{' -> stack.push(bracket);
                default -> {
                    char open = bracket == ')' ? '(' : bracket == ']' ? '[' : '{';
                    if (stack.isEmpty() || stack.pop() != open) return false;
                }
            }
        }
        return stack.isEmpty(); // anything left never got closed
    }

    static int[] dailyTemperatures(int[] temperatures) {
        // Monotonic stack: indexes of days still waiting for a warmer day, coldest on top. A
        // new day answers every colder day on top, then waits itself. Each index is pushed once
        // and popped at most once, so the nested loop is O(n) in total.
        int[] answer = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int waitingDay = stack.pop();
                answer[waitingDay] = i - waitingDay;
            }
            stack.push(i);
        }
        return answer; // days still on the stack keep 0
    }

    public static void main(String[] args) {
        check(isValid("([]{})"));
        check(!isValid("([)]"));
        check(!isValid("(("));
        check(Arrays.equals(
                dailyTemperatures(new int[] {73, 74, 75, 71, 69, 72, 76, 73}),
                new int[] {1, 1, 4, 2, 1, 1, 0, 0}));
        System.out.println("ok: isValid and dailyTemperatures");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

The monotonic stack has one decision: which comparison pops?

You want, for each element	Keep the stack	Pop while the top is
Next greater to the right	decreasing	smaller than the new element
Next smaller to the right	increasing	bigger than the new element
Previous greater to the left	decreasing	smaller or equal; the top after popping is the answer
Previous smaller to the left	increasing	bigger or equal; the top after popping is the answer

For “next” answers, the answer is assigned when an item is popped. For “previous” answers, it’s read from whatever is on top after popping, right before the new item is pushed.

Variations

Stack of state for nested decoding

Decode string turns 3[a2[c]] into accaccacc. On [, push the string built so far and the repeat count, and start fresh. On ], pop them and set the current string to previous + count × current. Each level of nesting is one stack frame, exactly what recursion would do, made explicit.

Min stack

Return the minimum in O(1) while pushing and popping. Store the minimum so far alongside every value, as a pair. When you pop, the minimum underneath comes back automatically. One stack of pairs is simpler and less bug-prone than two stacks kept in sync.

Largest rectangle in a histogram

Each bar extends left and right until it hits a shorter bar. An increasing stack finds both edges. When a bar is popped by a shorter one, the shorter bar is its right edge. The bar below it on the stack is its left edge. Push a height of 0 at the end, to flush everything out. It’s the hardest problem in this list, and the clearest proof that the pattern works.

Complexity

	Time	Extra memory
Valid parentheses, RPN, decode string	O(n)	O(n)
Any monotonic stack problem	O(n)	O(n)
Min stack, per operation	O(1)	O(n) total

Common mistake

Popping an empty stack

A closing bracket with nothing open, an operator with too few operands, or a while that forgets stack and .... Each one pops an empty stack. Python raises. Java’s ArrayDeque.pop throws. TypeScript’s pop quietly returns undefined. Always check before popping. And check at the end that the stack is empty when it should be. "((" is invalid, even though nothing went wrong in the middle of the loop.

Say this out loud

For each day I need the next warmer day. Days waiting for an answer can sit on a stack in decreasing order, and each new day answers the colder ones on top. Every day is pushed and popped once, so it’s O(n).

Interview questions

Interviewer asksThere's a while loop inside a for loop. Why is the monotonic stack O(n)?

Count pushes and pops instead of loop iterations. Each index is pushed exactly once, and can be popped at most once, because it’s never pushed again. The inner loop runs once per pop, so across the whole run it runs at most n times. Total work is O(n).

Interviewer asksWhy push indexes instead of temperatures?

The answer is a distance, i - waiting_day, so you need the position. You can always read the value back with temperatures[waiting_day], but you can’t recover a position from a value when values repeat. In histogram problems the index also gives the width.

Interviewer asksNext greater element in a circular array: how does the template change?

Loop over the array twice, from 0 to 2n - 1 for n numbers, using i % len(nums) as the index, and only push during the first pass. The second pass lets elements near the end find answers near the start. Elements still on the stack after both passes have no greater element.

Practice

10 problems on LeetCode: 2 easy, 7 medium, 1 hard

1. Valid Parentheses↗(opens LeetCode in a new tab)

   The most recent opener must close first.

   Easy
2. Next Greater Element I↗(opens LeetCode in a new tab)

   A decreasing stack pops each element when its answer arrives.

   Easy
3. Min Stack↗(opens LeetCode in a new tab)

   Store the minimum so far alongside each value.

   Medium
4. Evaluate Reverse Polish Notation↗(opens LeetCode in a new tab)

   Operands wait on the stack until their operator arrives.

   Medium
5. Daily Temperatures↗(opens LeetCode in a new tab)

   Keep waiting days on a stack; a warmer day answers all the colder ones.

   Medium
6. Asteroid Collision↗(opens LeetCode in a new tab)

   Only a left-mover meeting the top right-mover can collide.

   Medium
7. Decode String↗(opens LeetCode in a new tab)

   Push the partial string and count on "[" and pop on "]".

   Medium
8. Online Stock Span↗(opens LeetCode in a new tab)

   Pop smaller prices and absorb their spans into the new one.

   Medium
9. Car Fleet↗(opens LeetCode in a new tab)

   Sorted by position, a car that would arrive sooner joins the fleet ahead.

   Medium
10. Largest Rectangle in Histogram↗(opens LeetCode in a new tab)

    An increasing stack finds where each bar stops extending, on both sides.

    Hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

• Use a stack when the most recent unfinished item must be dealt with first: brackets, expressions, nesting.
• Use a monotonic stack for next or previous greater or smaller, spans and histogram areas.
• The rule: a new item pops everything it beats, and each pop is an answer.
• Cost: O(n), because every item is pushed and popped at most once.
• Watch for: popping an empty stack, and leftover items at the end (unclosed brackets, or elements with no answer).