Stacks: The Core Idea

Press undo in a text editor and the last thing you did disappears first. Press it again and the change before that goes. A browser's back button works the same way. Both keep a pile of things you might come back to, and they always hand back the most recent one.

That is a stack, and in interviews it has one job: it holds work you cannot finish yet, in the order you will be able to finish it. You meet something you cannot resolve — an open bracket, a number waiting for its operator, a day waiting for a warmer day — so you put it on the stack and move on. When the information that resolves it arrives, the item that needs it is the one on top.

The intuition: deferred work

Read the string {[( one character at a time. Three brackets are open, and none can be closed yet. Now ) arrives. Of the three open brackets, only one may legally be closed by it: the most recent one, (. The { was opened first and must be closed last.

That is LIFO exactly. The last thing opened is the first thing closed, because nesting works from the inside out. A queue, which hands back the oldest item, would give you { and get it wrong.

The same shape appears in problems with no brackets at all. In "for each day, how many days until a warmer one?", every day that has not yet seen a warmer day is waiting. When a warm day arrives, the waiting days it answers are the most recent ones, starting from the top. A stack answers each of them the moment its answer appears.

How to recognise it

The constraints give a second signal. "For each element, find the next element that…" has an obvious O(n²) answer: scan forward from every position. With n = 10⁵ that is 5 × 10⁹ comparisons, which is far too slow. A monotonic stack does the same job in O(n).

How it works

Every stack solution is the same loop: read the next input; if it resolves the item on top, pop and resolve (maybe several times); otherwise push it and move on. Here is that loop checking brackets in {[()]}. The rule: push every opener; on a closer, pop and check that the pair matches.

The stack ends empty, so every bracket found its partner: valid. Now ([)], the input that shows why a simple counter is not enough:

A counter of open brackets would see two openers and two closers and call it balanced. The stack remembers the order, and order is what the rules are about.

Two end conditions must both be checked, and forgetting either is the most common stack bug:

• Never pop an empty stack. In )(, the first character is a closer with nothing open. In Python, popping an empty list raises IndexError.
• Look at what is left at the end. In ((, every character was pushed and nothing failed, but two openers were never closed. The stack must be empty for the string to be valid.

The four shapes

A monotonic stack is the most valuable of these, and the one learners find hardest.

The templates

The matching template, for brackets mixed with other text:

1def is_balanced(text: str) -> bool:2    """True if every bracket in text is closed by the right type, in order."""3    opener_of = {")": "(", "]": "[", "}": "{"}   # closer -> the opener it needs4    openers = set(opener_of.values())5    stack: list[str] = []6    for ch in text:7        if ch in openers:8            stack.append(ch)                     # wait for the matching closer9        elif ch in opener_of:10            if not stack or stack.pop() != opener_of[ch]:11                return False                     # nothing open, or the wrong type12        # any other character is ignored13    return not stack                             # leftovers were never closed

Three decisions make every stack solution, and this template shows all three:

1. What goes on the stack? Here, the opening character. When the answer involves a position or a distance, push the index instead, and read the value with text[i] when you need it.
2. When do you pop? When the current input resolves the top item. Here, "the current character is a closer".
3. What are the end conditions? No pop on an empty stack, and a decision about leftovers.

The map goes from closer to opener, not the other way, because at the moment you need it you are holding a closer and asking "which opener should be on top?".

The monotonic template, for "next greater element to the right":

1def next_greater(nums: list[int]) -> list[int]:2    """For each value, the first bigger value to its right, or -1."""3    answer = [-1] * len(nums)4    stack: list[int] = []                    # indices still waiting; values decrease upward5    for i, value in enumerate(nums):6        while stack and nums[stack[-1]] < value:7            answer[stack.pop()] = value      # value is the answer for everything it pops8        stack.append(i)                      # i now waits for its own answer9    return answer

Line by line:

• answer = [-1] * len(nums). Elements that never find a bigger value keep -1. They are the ones still on the stack at the end.
• The stack holds indices. Here only the value is needed, but indices are never the wrong choice, and most problems need them.
• while stack and nums[stack[-1]] < value. Every waiting element smaller than value has just found its answer: value is the first bigger thing to its right. Pop them all. stack and comes first, so the empty stack is never read.
• stack.append(i). Now i waits. Everything below it on the stack is at least as big as nums[i], so the values decrease from bottom to top.

On [2, 7, 3, 5, 4, 6, 8], this returns [7, 8, 5, 6, 6, 8, -1]. When 6 arrives, the stack holds values 7, 5, 4; the 6 pops 4 and then 5, answering both, and stops at 7.

To choose the direction, do not memorise a table. Say this sentence: "pop the items that the current value answers." For "next greater", the current value answers everything smaller than it, so pop while the top is smaller. For "next smaller", pop while the top is bigger. For the answer to the left instead of the right, scan from right to left, or read the stack top just before you push.

Decide ties on purpose. With <, an equal value does not pop, so equal elements keep waiting for something strictly bigger. With <=, an equal value pops the earlier one and becomes its answer. "A warmer day" means strictly warmer, so it needs <.

Complexity

The while inside the for looks like O(n²). It is O(n), and the argument is short enough to say in an interview:

• Each index is pushed exactly once, by the append at the end of its own iteration.
• Each index is popped at most once, because once popped it is never pushed again.
• Every run of the while body is one pop.

So across the whole run, the while body executes at most n times in total — not n times per outer step. Total work: at most n pushes plus n pops, which is O(n). Space is O(n): a strictly decreasing input leaves everything on the stack.

The matching template is also O(n) time — one push and at most one pop per character — and O(n) space, for a string of all openers.

A stack can also replace recursion, since a recursive function's call stack is a stack. Recursion is shorter to write. An explicit stack cannot overflow, which matters in Python: the default recursion limit is about 1,000 frames, so a 100,000-deep chain needs a loop.

Where it goes wrong

1. Popping an empty stack. The input ) or, in Reverse Polish Notation, ["+"]. Every pop needs an emptiness check before it, and in a while condition, stack and … must come first.

2. Ignoring what is left at the end. (( returns True unless you check not stack. After the loop, ask what a non-empty stack means: in Valid Parentheses it means invalid; in Daily Temperatures it means "no warmer day", and the default 0 is correct.

3. Pushing values when you needed indices. In Daily Temperatures, a stack of temperatures tells you that a warmer day came, not how far away. If the answer is a position, distance or width, push indices.

4. The comparison pointing the wrong way. > instead of < builds the opposite stack. The code runs and returns plausible numbers, wrong for about half the elements. Test on [1, 2, 3] (next greater: [2, 3, -1]) and [3, 2, 1] ([-1, -1, -1]).

5. Popping operands in the wrong order. In ["5", "3", "-"], the top of the stack is the right operand, 3. Pop it first into a variable named right; the answer is 2, not -2.