Stacks and monotonic stacks

A stack is last in, first out: you add and remove from the same end, both in O(1). In Python it's just a list with append and pop. Anything nested, like brackets, function calls, folders or undo history, tends to be a stack problem, because the most recent thing you opened is the first thing you close.

Checking brackets is the classic: push every opening bracket, and on every closing one, pop and check it matches. If the stack's empty when you need to pop, or not empty at the end, it's unbalanced.

A monotonic stack is a stack you keep in sorted order by popping anything that breaks the order. It answers "what's the next bigger value to the right of each element?" in one pass. Each position waits on the stack until something bigger shows up and pops it:

def next_greater(values):
    answer = [-1] * len(values)
    stack = []  # positions still waiting for something bigger
    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            answer[stack.pop()] = value
        stack.append(i)
    return answer

It looks like a nested loop, but every position is pushed once and popped at most once, so the whole thing is O(n).

• Look for nesting, matching pairs, undo, or "the next bigger or smaller thing".
• Say what's on the stack and what order it's kept in.
• Explain why the popping loop doesn't make it O(n²).

Daily temperatures

Given daily temperatures like [73, 74, 75, 71, 69, 72, 76, 73], return how many days you'd wait for a warmer one, for each day. Use 0 if a warmer day never comes.

1. The brute force checks every later day for each day, which is O(n²).
2. Notice that it's 'next greater element', but you want the distance, not the value. So keep positions on the stack.
3. Walk left to right. Before pushing today, pop every day on the stack that's colder than today. Each of those just found its answer: today's position minus theirs.
4. On day 5 (72): the stack holds days 2, 3, 4 (75, 71, 69). 69 and 71 are colder, so day 4 waits 1 day and day 3 waits 2. 75 isn't colder, so it stays.
5. On day 6 (76): days 5 and 2 are colder, so they wait 1 and 4 days.
6. Anything left on the stack at the end never found a warmer day, so it stays 0.
7. The answer is [1, 1, 4, 2, 1, 1, 0, 0]. Every day is pushed once and popped at most once, so it's O(n).

Things interviewers tend to ask once you've brought this up.

How would you evaluate '3 + 4 * 2 - 1'?

Keep a stack of numbers. Multiply or divide into the top of the stack straight away, push numbers after a plus, and push negated numbers after a minus. Sum the stack at the end.

What's the minimum number of brackets to remove to make a string valid?

Push positions of '(' and pop on ')'. A ')' with nothing to pop has to go, and any '(' left on the stack at the end has to go.

How do you build a stack that returns its minimum in O(1)?

Store each item along with the minimum so far. The top always knows the current minimum.

How do you simplify a path like /a/./b/../c?

Split on '/', skip empty parts and '.', pop on '..', and push everything else. Join what's left.

• Popping from an empty stack.
• Forgetting to check the stack is empty at the end.
• Storing values when you need positions, or the other way round.
• Calling a monotonic stack O(n²) because there's a loop inside a loop.
• Getting the comparison backwards, so the stack keeps the wrong order.

• Trees and recursionSolve tree problems by deciding what each node returns.
• Hash maps and sliding windowsSwap nested loops for a single pass.
• BacktrackingTry every option, and stop early on the ones that can't work.