Stack

When to reach for it

• Nested structure: brackets, tags, folders, expressions, document outlines.
• Most-recent-first behavior: undo, back navigation, call frames.
• For each element, the nearest larger or smaller element to one side: the next warmer day, a price span.
• Evaluating expressions where operators have precedence.
• Turning a deep recursion into a loop with an explicit stack.

The core idea

Push when something opens or starts waiting for an answer; pop when you find what closes or answers it. If the input is well formed, everything is popped exactly once and the stack is empty at the end. If you meet a closer with nothing to match, or finish with items left over, the input is malformed, and the position tells you where.

A monotonic stack keeps its items in increasing or decreasing order. When a new value arrives, it pops every item it outranks, and for each popped item the new value is its answer. Whatever is still on the stack at the end has no answer. Each index is pushed once and popped at most once, so the scan is O(n) however many pops a single step makes.

A Python template

def simplify_path(path):
    stack = []
    for part in path.split("/"):
        if part == "..":
            if stack:
                stack.pop()              # step back out of the latest folder
        elif part and part != ".":
            stack.append(part)           # step into a folder
    return "/" + "/".join(stack)

def spans(prices):
    """For each day, how many consecutive days up to it had a price <= it."""
    out, stack = [], []                  # indexes, prices strictly decreasing
    for i, p in enumerate(prices):
        while stack and prices[stack[-1]] <= p:
            stack.pop()                  # today outlasts every popped day
        out.append(i - stack[-1] if stack else i + 1)
        stack.append(i)
    return out

The first function is the matching shape: the latest open folder is on top. The second is the monotonic shape: the stack holds the days still higher than everything after them, so each day's answer is the distance to the first one still standing.

Time and space

Matching is O(n) time, with up to O(n) stack space when everything opens before anything closes. The monotonic stack is O(n) time as well, because each index is pushed and popped at most once; its space is O(n) in the worst case, a strictly decreasing input.

Common mistakes

• Popping from an empty stack when a closer arrives first.
• Declaring success without checking that the stack is empty at the end, which accepts an unclosed opener.
• Storing values when you need positions; store indexes and look the values up.
• Choosing < where <= is needed in a monotonic stack, which changes how equal values are treated.
• Forgetting the items left at the end, which still need a default answer.

How to explain it out loud

Say what lives on the stack and why: "The stack holds days that haven't been outlasted yet, highest price at the bottom." Then explain one pop: "When today's price is at least as high, it outlasts the day on top, so I pop it." Those two sentences carry the whole algorithm and tell the interviewer you are not pattern-matching blindly.

Justify the cost before you are asked, since the nested loop looks quadratic: "Each index is pushed and popped once, so it's O(n)." Then mention the empty input, equal values and the leftovers. Answering "why isn't this O(n squared)?" crisply when Josh asks is what Devana scores as code defense.