Stacks

The question

Is this string of brackets valid? ([]{}) is. ([)] is not. Every opener must be closed by the matching closer, in the right order. That is the warm-up. The same tool then answers “for each day, how long until a warmer one”, and “what does 3[a2[c]] expand to”.

Explain it to a ten-year-old

A pile of plates. You can put a plate on top or take the top one off. You cannot pull one out of the middle. Now read the brackets left to right. Every time you see an opener, put a plate on the pile with that shape drawn on it. Every time you see a closer, look at the top plate. If it is the matching opener, take it off. If it is the wrong shape, or there is no plate, the string is broken. When you reach the end, the pile must be empty.

The trick

A stack is the answer whenever the thing you need next is the most recent thing you have not dealt with yet. Brackets: the closer must match the most recent unclosed opener. Undo: the most recent edit. Nested strings: the most recent unfinished group. “Next warmer day”: the most recent day still waiting for an answer.

Three shapes cover nearly every stack problem:

1. Match. Push openers. On a closer, pop and compare. Empty at the end means valid.
2. Unwind. Push partial work as you go into nesting. On the way out, pop and combine. Decode String, expression evaluation, folder paths.
3. Monotonic. Keep the stack sorted, say decreasing. When a newcomer is bigger than the top, pop, and the newcomer is the answer for everything you popped. Next greater element, daily temperatures, largest rectangle.

The steps

Valid Parentheses:

1. pairs = {")": "(", "]": "[", "}": "{"}, stack = [].
2. For each character: if it is an opener, push it. If it is a closer, the stack must be non-empty and its top must be pairs[c]. Otherwise return false. Pop.
3. Return not stack.

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

Time O(n). Space O(n) in the worst case, a string of all openers.

Daily Temperatures, the monotonic shape:

def daily_temperatures(t):
    ans = [0] * len(t)
    stack = []                        # indices, temperatures decreasing from bottom to top
    for i, x in enumerate(t):
        while stack and t[stack[-1]] < x:
            j = stack.pop()
            ans[j] = i - j            # x is the first warmer day after j
        stack.append(i)
    return ans

Each index is pushed once and popped at most once, so O(n) even with the inner while.

The template

Someone worked out the three shapes years ago. Memorise them as one loop with the capitals filled in differently, and understand what the stack is holding in each. That last part is what lets you use it on a problem you have not seen.

stack = []
for x in INPUT:
    while stack and SHOULD_POP(stack[-1], x):   # match: closer meets its opener. monotonic: x beats the top
        top = stack.pop()
        RESOLVE(top, x)                         # match: nothing. monotonic: x is top's answer. unwind: combine
    if SHOULD_PUSH(x):                          # match: openers only. monotonic: always. unwind: on the way in
        stack.append(x)
FINISH(stack)                                   # match: must be empty. monotonic: leftovers have no answer

The question to ask before writing any of it is what does each item on the stack mean. In matching, an opener waiting for its closer. In unwinding, work paused while you go one level deeper. In a monotonic stack, an item still waiting for its answer, and the stack stays sorted because anything that would have broken the order has already been answered and removed. If you can say what a stack item means, the pops write themselves. If you cannot, you are guessing.

In GPU infrastructure

A safe rollout is a stack. Each step pushes its undo, and a failure pops until the node is clean again. Parsing the nested output of a topology dump or an nvidia-smi query is the unwind shape, and the bracket check is how you know a config template is well formed before it reaches a thousand hosts. The monotonic stack answers “for each minute, how long until throughput was next higher”, which is the shape of a straggler report over time.

What I am listening for

• Whether you check the stack is non-empty before you look at the top. Every stack bug I have ever seen in an interview is this one.
• Whether you match the type, not just the count. ([)] has balanced counts and is wrong.
• For the monotonic shape, whether you can say why the inner while does not make it n squared. Each item is popped once. If you cannot say that, you cannot defend the complexity.
• Whether you know what is on the stack. I ask “what does the top of your stack mean right now” halfway through. The good candidates answer in one sentence.

Where it leads

Match:

• Valid Parentheses. The one above.
• Min Stack. A stack that also answers “smallest right now”. A second stack does it.

Unwind:

• Decode String. Push the count and the string so far on [, pop and repeat on ].
• Evaluate Reverse Polish Notation. Push numbers, an operator pops two.
• Simplify Path. .. pops a folder.

Monotonic:

• Daily Temperatures. The snippet above.
• Next Greater Element I. The same, with a map at the end.
• Largest Rectangle in Histogram. Increasing stack of bar indices. Popping a bar tells you how far its height extends. The hard one.
• Sliding Window Maximum. The monotonic idea in a deque, because items also leave from the front.

Go deeper

• Stack overview on Hello Interview, and their monotonic stack page for the third shape.
• Valid Parentheses and Daily Temperatures walked through by NeetCode. The second one is where the monotonic idea clicks for most people.
• Stack problems on LeetCode and the monotonic stack list. Do Valid Parentheses, Daily Temperatures and Decode String in one sitting and you have seen all three shapes.
• Stack on Wikipedia for the two minutes of history, including why it is called push and pop.

With AI on the table. The assistant writes Valid Parentheses in one go. I hand it Daily Temperatures and ask it for the complexity. It says O(n). I ask you whether that is right, and why, with a while loop inside a for. The answer is “each index is popped once”. If you cannot say it, the tool’s answer is a rumour.