What Does a Stack Actually Remember in the Valid Parentheses Problem?

You probably can write the ten‑line solution that pushes on a left bracket and pops on a matching right bracket, but the interview may ask: what exactly is the stack storing?

Stack stores expectations, not characters

Each left bracket creates an expectation that a corresponding right bracket will appear later; this expectation is pushed onto the stack. When a right bracket arrives, it is compared only with the top expectation. If they match, the expectation is fulfilled and popped; otherwise the string is invalid.

Why a stack, not a counter?

A counter only tracks the number of unmatched brackets and loses ordering information. For a crossing pattern like "([)]", the counts are equal but the nesting is illegal; the stack detects this because the top expectation (a right square bracket) does not match the incoming right parenthesis.

Concrete implementation

def isValid(s: str) -> bool:
    # right bracket -> the left bracket (expectation) it can close
    closes = {')': '(', ']': '[', '}': '{'}
    stack = []  # stack holds "unfulfilled expectations"
    for ch in s:
        if ch in closes:
            # right bracket: does it close the top expectation?
            if not stack or stack[-1] != closes[ch]:
                return False
            stack.pop()  # expectation fulfilled
        else:
            stack.append(ch)  # new expectation
    return not stack  # non‑empty stack means leftover expectations → invalid

The expression stack[-1] is the crucial "look at the top" operation.

Don't forget the final check

Even if every right bracket matched, the string is invalid when the stack is non‑empty after the loop (e.g., "(("). The final return ensures all expectations are fulfilled.

Interview follow‑up questions

If the string contains only one type of bracket, a counter suffices and space drops to O(1). If asked for the length of the longest valid substring, the stack stores indices instead of characters. Variations may include expressions with operators, or asking for the minimum deletions to make the string valid – all solvable by interpreting the stack contents appropriately.

Conclusion

The real value of the "valid parentheses" problem lies not in writing ten lines of code, but in understanding that the stack records pending expectations, a pattern that recurs in many interview problems.