Stack

In ([]), ] must match the most recent [. A stack stores unfinished work. Study matching, monotonic stacks and calculators separately, defining what each entry represents.

Two principles hold throughout this article:

1. First say exactly what the stack holds. It holds things that aren't finished and are waiting for some later element to deal with them, and the top is the most recent of them: "unmatched opening brackets", "indices still waiting for a warmer day", "asteroids still alive". Whether to store values or indices is decided at this point too.
2. The moment an element is popped is the moment its answer becomes known. Compute the answer where you pop. A popped element never comes back, so every element is pushed at most once and popped at most once, and a while inside a for is still O(n).

The article goes in this order, and each step adds exactly one idea to the previous one:

When to Use This Pattern

Many brute-force solutions scan backward (or forward) from every element looking for its match, the first larger value, or whatever cancels it: O(n²). It's slow because every element rescans from scratch, and nothing learned from earlier scans is kept.

Take "how many days until a warmer day" (LC 739) with temps = [73, 71, 69, 72]:

Before 72 arrives, the days 73, 71 and 69 are all still waiting for a warmer day. They line up in order, with the most recent, 69, on top. When 72 arrives, it settles 69 first, then 71, and stops at 73, which is larger. What gets settled is always "the most recent one still waiting", which is a stack. Each day is pushed once and popped once, so the whole thing is O(n).

The test: while scanning left to right, do you keep looking back at the most recent unfinished element on the left? If so, use a stack.

Recognition Checklist

• The input has brackets, paths, or expressions, and handling the current character depends on "the most recent thing that hasn't closed"
• Adjacent elements cancel or collide, and the new neighbors may cancel again
• For each element you need the first larger (smaller) element on its left or right, or the distance or width to it
• You evaluate an expression with operator precedence, or expand a nested structure
• Design: a stack or queue that also supports O(1) getMin, most-frequent-first pop, and similar operations

Before You Code

Before writing stack code, answer these three questions:

1. What does the stack hold? Say "who is waiting for what" in one sentence: unmatched opening brackets, indices that haven't found their next larger value, asteroids still alive. If you need distances or widths, store indices.
2. When does a new element resolve the top, and what do you compute when you pop? Matching it, being larger than it, destroying it all count as resolving. The answer is computed at that pop. If the new top might be resolved too after one pop, write a while; otherwise an if.
3. When do you push, and what do you do with what's left at the end? Push when the current element doesn't have its result yet and must wait for someone later. Leftovers: in bracket problems they mean invalid; in a monotonic stack they have no answer, so fill in a default or append a sentinel that forces them out; in cancellation problems they are the result.

Question 1 fixes the meaning of the stack, and questions 2 and 3 are the pop rule and the push rule under that meaning. Once all three answers are written down, the code mostly copies them.

Try it on LC 735 Asteroid Collision.

The input is a row of asteroids given as nonzero integers: the absolute value is the size, positive moves right, negative moves left, and all move at the same speed. When two collide, the smaller one explodes; equal sizes both explode. Return the asteroids still alive after all collisions, as an array in left-to-right order.

For example [10, 2, -5] → [10]: -5 first destroys 2, then hits 10 and explodes itself. You return the survivors, not a collision count.

The three answers:

• What the stack holds: the asteroids still alive so far, left to right.
• When the top is resolved: at equal speeds, only "the left one moving right, the right one moving left" collide, that is, "current moving left, top moving right". If the top is smaller, it explodes and is popped; the current asteroid keeps moving left and will hit the new top, so it's a while. Equal sizes both explode; if the top is bigger, the current one explodes.
• When to push, and the leftovers: if the current asteroid survives its collisions, push it. At the end the stack is the answer.

Step 2 turns this into code.

Valid Parentheses (LeetCode 20)

Given a string over ()[]{}, return whether bracket types match with proper nesting. Equal opening/closing counts alone are insufficient: ([)] is False. This trace validates one supplied string rather than generating all valid strings.

Input: s = "([]{})". Expected: True.

The stack holds the opening brackets that are still waiting for their partner.

1. Walk it by hand

2. Read the rule off the table

• An opening bracket is always pushed.
• A closing bracket must match the top of the stack. If it matches, pop; if the stack is empty or the top is different, the string is invalid.
• At the end the string is valid only if the stack is empty.

3. Turn each row into code

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

Core Templates

Every step uses the same approach: answer the three questions, then check against the two principles at the top. Does the stack's meaning hold at every step? Is the answer computed at the moment of popping?

In Python a stack is just a list: append(x) pushes, pop() removes and returns the top, stack[-1] peeks (index -1 is the last element), all O(1). An empty list counts as False in an if, so if not stack means "the stack is empty". Check for empty before peeking or popping; on an empty list stack[-1] raises IndexError.

Step 1: A New Element Only Deals With the Top

Problem: decide whether a string of ()[]{} has properly matched and nested brackets (LC 20).

The input is a string of only those six characters; return True or False. Valid means: every closing bracket matches the most recent still-unmatched opening bracket, of the same kind, and no opening bracket is left over at the end.

For example "([])" → True. "([)]" → False: the counts are equal, but when ) arrives the most recently opened bracket is [, so the nesting is wrong.

LeetCode guarantees a nonempty input; the code below returns True for an empty string, which is an extra case.

The three questions:

• What the stack holds: unmatched opening brackets, with the most recently opened on top.
• When the top is resolved: a closing bracket can only match the most recently opened bracket, which is the top. If it matches, pop. If the stack is empty, or the top is a different kind of opening bracket, the string is invalid.
• Push and leftovers: every opening bracket is pushed. If any remain at the end, some bracket never closed, so the string is invalid.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}   # closer -> the opener it needs
    stack = []                          # unmatched opening brackets
    for ch in s:
        if ch in pairs:                 # `in` on a dict checks the keys: is ch a closer?
            if not stack or stack[-1] != pairs[ch]:   # check for empty before peeking
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack                    # valid only if empty; leftovers are openers that never closed


assert is_valid("([]{})") is True
assert is_valid("([])") is True         # the example from the statement
assert is_valid("([)]") is False
assert is_valid(")") is False
assert is_valid("((") is False
assert is_valid("") is True

The stack after each character of "([]{})":

The stack is empty at the end, so it returns True. Here are the common mistakes:

A counter knows how many, not in what order. When ) arrives you need to know which kind of bracket was opened most recently, and only the top has that information.

Variation: simplify a Unix path (LC 71)

The input is an absolute Unix path starting with /. Return the simplified canonical path.

Rules: several / in a row count as one; . means the current directory, .. means the parent directory, and going above the root stays at the root; a segment is special only if it is exactly . or .., so ... is an ordinary directory name. The result starts with /, has exactly one / between directories, and has no trailing /.

For example "/a//b/../c/." → "/a/c": enter a, enter b, .. goes back to a, enter c, . stays.

Think first: What is "the most recent unfinished thing" here? Which stack operation does .. correspond to? How should ., the empty segments from repeated /, and a .. at the root each be handled?

def simplify_path(path):
    stack = []                          # directory levels from the root down
    for part in path.split("/"):
        if part == "..":
            if stack:                   # already at the root: stay
                stack.pop()
        elif part and part != ".":      # empty string is False: from repeated slashes; dot means stay
            stack.append(part)
    return "/" + "/".join(stack)


assert simplify_path("/a//b/../c/.") == "/a/c"   # the example from the statement
assert simplify_path("/a/./b/../../c/") == "/c"
assert simplify_path("/home//foo/") == "/home/foo"
assert simplify_path("/../") == "/"
assert simplify_path("/...") == "/..."

Variation: baseball game (LC 682)

The input is a list of operation strings. Keep score in order and return the sum of all scores that are still valid at the end. Each operation is one of four kinds:

• An integer (possibly negative): record that score.
• "C": the previous score is cancelled and removed.
• "D": record a new score, twice the previous valid score.
• "+": record a new score, the sum of the previous two valid scores.

The scores that C, D and + need are guaranteed to exist.

For example ["5", "2", "C", "D", "+"] → 30: record 5, record 2, C removes 2, D records 10, + records 5 + 10 = 15, so the valid scores are 5, 10, 15 and the sum is 30. You return the sum, not the list of scores.

Think first: Which earlier scores do C, D and + each use? Once C cancels a score, can a later + still use it? So what should the stack hold?

def cal_points(ops):
    stack = []                          # scores that are still valid
    for op in ops:
        if op == "+":
            stack.append(stack[-1] + stack[-2])   # the two most recent valid scores
        elif op == "D":
            stack.append(2 * stack[-1])
        elif op == "C":
            stack.pop()                 # cancel the most recent score
        else:
            stack.append(int(op))       # int("-2") converts straight to -2
    return sum(stack)


assert cal_points(["5", "2", "C", "D", "+"]) == 30   # the example from the statement
assert cal_points(["5", "-2", "4", "C", "D", "9", "+", "+"]) == 27
assert cal_points(["1", "C"]) == 0

Step 1 recap

• What it solves: how to handle the current element depends only on "the most recent unfinished thing", for example a closing bracket can only match the most recently opened one.
• The key line: if not stack or stack[-1] != pairs[ch]: return False, checking for empty before peeking.
• What the variations change: what the stack holds (unmatched openers, current directory levels, valid scores), and what triggers a pop (.. or C).
• Easiest mistake: forgetting the empty check, or forgetting to check for leftovers at the end. Test with ")" and "((".

In this step a new element resolves at most one top. In some problems, after one pop the new top must be compared with the current element again. That's Step 2.

Step 2: Pops Can Chain, So Write a While

Problem: asteroid collision (LC 735), the one walked through in "Before You Code".

The statement once more: given an array of nonzero integers, the absolute value is the size, positive moves right and negative moves left, all at the same speed. Return the asteroids still alive after all collisions, left to right.

For example [10, 2, -5] → [10]. [-2, 1] → [-2, 1]: -2 moves left and 1 moves right, flying apart, so they never collide.

The three answers are already written. There's only one difference from Step 1: after the current asteroid destroys the top it may still be alive and go on to hit the new top, so popping is a while. An alive flag records whether the current asteroid still exists:

def asteroid_collision(asteroids):
    stack = []                          # asteroids still alive, left to right
    for x in asteroids:
        alive = True                    # whether the current one still exists
        while alive and x < 0 and stack and stack[-1] > 0:   # only current-left, top-right collide
            if stack[-1] < -x:          # -x is the current asteroid's size
                stack.pop()             # top explodes, x goes on to hit the next one
            elif stack[-1] == -x:
                stack.pop()             # same size, both explode
                alive = False
            else:
                alive = False           # top is bigger, x explodes
        if alive:
            stack.append(x)
    return stack


assert asteroid_collision([10, 2, -5]) == [10]
assert asteroid_collision([-2, 1]) == [-2, 1]   # the example from the statement: moving apart
assert asteroid_collision([5, 10, -5]) == [5, 10]
assert asteroid_collision([8, -8]) == []
assert asteroid_collision([-2, -1, 1, 2]) == [-2, -1, 1, 2]
assert asteroid_collision([1, -2, -2, -2]) == [-2, -2, -2]

[10, 2, -5]:

With an if instead, -5 destroys 2 and is then pushed, giving [10, -5] and missing its collision with 10. [-2, -1, 1, 2] is worth a look too: the left-movers are on the left and the right-movers on the right, flying apart, so nothing ever collides. The collision condition is "current moving left, top moving right", not "different signs".

Variation: remove adjacent duplicates entirely, and keep removing

Practice here (original problem) ↗

The input is a string. Whenever two or more equal characters sit next to each other, delete that whole run, keeping none of them; then keep deleting any equal characters that become adjacent, until nothing more can be removed. Return the final string.

For example "abbbbazw" → "zw": the 4 b's in the middle all go, which makes the two a's adjacent, so they go too.

This differs from LC 1047, which deletes one pair at a time: in "aaab" it removes one pair of a's and leaves "ab", while here the whole run of a's goes and "b" is left.

Think first: As with the asteroids, after a run is deleted, who becomes neighbors with whom? What does the stack hold? When the current character equals the top, which characters must go, and does the top itself stay?

def remove_adjacent_stack(s):
    stack = []                          # characters kept so far
    j = 0                               # next character to process
    while j < len(s):
        if stack and s[j] == stack[-1]:
            while j < len(s) and s[j] == stack[-1]:
                j += 1                  # skip the whole run equal to the top
            stack.pop()                 # and drop the top itself
        else:
            stack.append(s[j])
            j += 1
    return "".join(stack)               # glue the list of characters into a string


assert remove_adjacent_stack("abbbbazw") == "zw"   # the example from the statement
assert remove_adjacent_stack("aaab") == "b"        # unlike LC 1047: the whole run goes
assert remove_adjacent_stack("abba") == ""
assert remove_adjacent_stack("aab") == "b"
assert remove_adjacent_stack("abc") == "abc"
assert remove_adjacent_stack("") == ""

Variation: use the left part of the array as the stack instead of a list

Practice here (original problem) ↗

Same problem as above, but in place: no separate list as the stack; the result is written into the front of the input array itself.

Think first: The code above uses only four stack operations: peek, push, pop, and empty check. If the kept result lives in the left part of the array, a[:i], what does each of those four become?

def remove_adjacent_inplace(s):
    a = list(s)                         # strings are immutable, so use a list of characters
    i = 0                               # a[:i] is the stack, a[i-1] is the top
    j = 0                               # next character to process
    while j < len(a):
        if i > 0 and a[j] == a[i - 1]:
            while j < len(a) and a[j] == a[i - 1]:
                j += 1
            i -= 1                      # pop
        else:
            a[i] = a[j]                 # push
            i += 1
            j += 1
    return "".join(a[:i])


assert remove_adjacent_inplace("abbbbazw") == "zw"
assert remove_adjacent_inplace("abba") == ""
assert remove_adjacent_inplace("aab") == "b"
assert remove_adjacent_inplace("") == ""

Step 2 recap

• What it solves: after the top is popped the current element is still there and must be compared with the new top, for example an asteroid that destroys one and goes on to hit the next.
• The key line: while alive and x < 0 and stack and stack[-1] > 0:, popping in a while, with a flag for whether the current element still exists.
• What the variations change: collision becomes "equal to the top, delete the whole run"; then the list becomes the left part of the array a[:i], where i -= 1 is the pop.
• Easiest mistake: writing an if and popping only once. Test with [10, 2, -5]: the if version returns [10, -5].

Up to this step, nothing is required about the order of values in the stack. The next step requires the values in the stack to stay monotonic, so that at the moment of popping you can read off "the first larger element to the right" directly.

Step 3: Monotonic Stack, the Answer Is Known at Pop Time

Problem : daily temperatures ( LC 739 ). The input is an array temps of daily temperatures. (Pro lesson)

Variation: online stock span (LC 901)

Implement a class StockSpanner . Each day you call next(price) with today's price, and it returns today's "span": counting back from today,… (Pro lesson)

Variation: car fleet (LC 853)

n cars on a single-lane road drive toward target . (Pro lesson)

Variation: number of visible people in a queue (LC 1944)

n people stand in a line from left to right; the input is their heights heights (all distinct). Each person looks only to the right. (Pro lesson)

Step 3 recap

What it solves : for each element, the first larger (smaller) element on one side, or the distance to it. (Pro lesson)

Step 4: Left and Right Boundaries from a Monotonic Stack

Problem : the largest rectangle in a histogram ( LC 84 ). The input is an array heights of nonnegative integers; (Pro lesson)

Variation: the largest rectangle of 1s in a 0/1 matrix (LC 85)

The input is a matrix of the characters "0" and "1" . Return the area of the largest rectangle containing only "1" . (Pro lesson)

Step 4 recap

What it solves : for each element, the first smaller element on both sides at once, for example how far each bar extends in both directions.… (Pro lesson)

Step 5: Two Stacks, Deferred Evaluation

Problem : evaluate reverse Polish notation ( LC 150 ). Reverse Polish notation writes each operator after its two operands; (Pro lesson)

One step further: an ordinary infix expression (LC 772 Basic Calculator III)

The input is a valid ordinary expression string (each operator between its two operands) with nonnegative integers, + - * / , parentheses an… (Pro lesson)

Variation: decode string (LC 394)

The input is a valid encoded string; return the decoded string. (Pro lesson)

Step 5 recap

What it solves : park what can't be computed yet on a stack, and pop it once it can be, for example an operator waiting to see whether a hig… (Pro lesson)

Step 6: Auxiliary Stacks for Design Problems

Problem : Min Stack ( LC 155 ). Implement a class MinStack with four operations, each O(1): push(val) : push val onto the stack. (Pro lesson)

Variation: a queue from two stacks (LC 232)

Using only stacks (push, pop, peek, empty check), implement a queue class MyQueue with: push(x) : add x to the back. (Pro lesson)

Variation: a stack from one queue (LC 225)

The other way around: using only a queue (add to the back, remove from the front, peek at the front, size, empty check), implement a stack c… (Pro lesson)

Variation: maximum frequency stack (LC 895)

Implement a class FreqStack with: push(val) : push val onto the stack. (Pro lesson)

Step 6 recap

What it solves : a stack or queue that also answers a statistic in O(1) (minimum, highest frequency), or one structure simulating another. (Pro lesson)

The Six Steps Side by Side

Step What the stack holds When to pop What to do on pop Leftovers at the end Step 1 Unmatched openers, current directory levels a closer mat… (Pro lesson)

One Problem, Many Disguises

The statements of these problems come first; the table after them shows which core problem each one disguises. (Pro lesson)

Common Pitfalls

Peeking or popping an empty stack. On input ")" , going straight to stack[-1] raises IndexError. Fix: check if not stack or ... first. (Pro lesson)

Say It in the Interview

After confirming that bar heights are non-negative and whether the array can be empty, you could explain Largest Rectangle in Histogram ( LC… (Pro lesson)