Stacks: Matching, Evaluating, Remembering

What a stack is

A stack is a list you touch at only one end. You push (add) on top, you pop (remove) from the top, and you can peek at the top without removing it. All three are O(1). The last thing pushed is the first thing popped — "Last In, First Out", or LIFO.

That one restriction is the point. A stack is the right tool whenever the rule of the problem is: the most recent unfinished thing is the next thing to deal with. Nested brackets, undo history, and function calls all follow that rule — which is why your language's call stack is literally a stack.

Interview signal words: "nested", "matching pairs", "most recent", "previous/next greater or smaller", "evaluate this expression".

Use 1: Matching nested things

Take "([{}])". When you reach }, which bracket must it close? The most recently opened bracket that is not yet closed — here {. Closers always pair with the newest outstanding opener, so a stack models it exactly:

• See an opener → push it. It is a promise to be closed later.
• See a closer → the stack top must be its matching opener. Pop it. If the stack is empty or the top is the wrong type, the string is invalid.
• At the end, the stack must be empty — leftovers are openers nobody ever closed.

Three distinct ways to fail, and all three appear as test cases in Valid Parentheses: wrong type ("(]"), wrong order ("([)]" — when ) arrives the top is [), and unclosed leftovers ("(").

Use 2: Evaluating postfix expressions

Postfix (also called Reverse Polish Notation, or RPN) writes the operator after its two operands: 3 4 + means 3 + 4. No parentheses are ever needed, and a stack evaluates it in one pass:

• Number → push it.
• Operator → pop two numbers, apply the operator, push the result.

Worked example, ["2", "1", "+", "3", "*"] (which is (2 + 1) * 3):

One classic trap: order matters for - and /. The first pop is the right-hand operand, the second pop is the left. a b - means a - b, so compute second_pop - first_pop.

Use 3: Remembering extra state (the auxiliary stack)

Min Stack asks for push, pop, top, and getMin, all in O(1). A single "current minimum" variable breaks the moment you pop the minimum — what was the minimum before it?

Answer: remember the minimum at every level. Keep a second stack that moves in lockstep with the main one; its top is always "the minimum of everything currently in the stack".

def push(self, val):
    self.stack.append(val)
    cur_min = min(val, self.mins[-1]) if self.mins else val
    self.mins.append(cur_min)

def pop(self):
    self.stack.pop()
    self.mins.pop()   # the old minimum is restored automatically

Push 5, 2, 7: the min stack reads [5, 2, 2]. Pop the 7, then the 2 — the min stack pops back to [5], and getMin is 5 again with zero recomputation. The general idea: a stack can carry history you would otherwise have to recompute.

Use 4: The monotonic stack

This is the pattern interviews actually test. Whenever a problem asks for the nearest greater (or smaller) element to the left or right of each position — "next warmer day", "previous smaller price", "how far until a taller building" — the answer is a monotonic stack: a stack that keeps its contents sorted by evicting anything that would break the order before each push.

Here is next-greater-to-the-right. The stack holds indices, and their values always read in decreasing order from the bottom of the stack to the top — each new value pops everything smaller than itself before joining:

def next_greater(a):
    answer = [-1] * len(a)
    stack = []                      # indices; values decrease bottom -> top
    for i in range(len(a)):
        while stack and a[stack[-1]] < a[i]:
            j = stack.pop()
            answer[j] = i           # a[i] is the next greater for a[j]
        stack.append(i)
    return answer                   # leftovers keep -1: nothing greater

Why it works: when a[i] pops a[j], every value between them was already popped for being even smaller — so a[i] is the first greater value to j's right. And each index is pushed once and popped at most once, so the whole scan is O(n) despite the nested-looking loop.

Trace on temperatures [73, 74, 75, 71, 69, 72]:

• 74 pops 73 (73's answer: index 1). 75 pops 74. Stack: [75].
• 71, 69 are smaller — both push. Stack: [75, 71, 69].
• 72 pops 69, then 71 (both get answer index 5), but not 75. Stack: [75, 72].
• 75 and 72 never get popped → no warmer day, answer stays -1.

Four decisions to make deliberately

1. Store indices, not values. Distances ("how many days until warmer") need indices; you can always read the value back with a[i].
2. Strict vs non-strict comparison. Popping on < vs <= changes answers when duplicates exist. Decide which the problem wants before coding.
3. Flush the leftovers. Anything still on the stack at the end has no "next greater". In Largest Rectangle in Histogram, the standard trick is appending a sentinel bar of height 0 so everything gets popped and processed.
4. Direction flips are symmetric. Next smaller instead of greater? Flip the comparison. Nearest to the left instead of right? The element below you on the stack at push time is your answer. Same machine, four variants.