Stack Pattern: Template + 194 LeetCode Problems

What the stack pattern is

A stack is the right structure whenever the most recent unresolved item is the one a new element interacts with — which is another way of saying the input is nested. Brackets, directory paths, HTML tags, arithmetic expressions and undo histories are all the same problem: push when something opens, pop when the thing that closes it arrives, and the input is well-formed exactly when the pop matches and the stack ends empty. Both failure modes matter and both are commonly missed — a closing token arriving at an empty stack is as wrong as leftover items at the end. The second use is deferring work rather than matching it: an explicit stack is how a recursive traversal is rewritten iteratively when recursion is forbidden or the depth would overflow, and the only subtlety is that children must be pushed in reverse order to be visited in the intended one. When the stack additionally has to stay sorted, it becomes a monotonic stack, which is a different pattern with a different purpose.

When to use it

• —The input nests: brackets, tags, paths, expressions, nested encodings.
• —A new element resolves against the most recent unmatched one rather than the oldest.
• —A recursive solution exists but recursion is banned or would exceed the depth limit.
• —Work has to be undone, or evaluated in the reverse of the order it arrived.

The stack template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 194 problems listed below.

def is_balanced(s):
    closing = {")": "(", "]": "[", "}": "{"}
    stack = []

    for char in s:
        if char in closing:
            if not stack or stack.pop() != closing[char]:
                return False       # closed something that was never opened
        else:
            stack.append(char)

    return not stack               # anything still open is unbalanced

Complexity characteristics

Time

O(n)

Auxiliary space

O(n)

A single pass that pushes and pops each token at most once. The stack grows to the maximum nesting depth, which is n for an input that opens everything before closing anything, so the worst-case space is linear even when the typical case is shallow. Rewriting a recursion with an explicit stack changes neither figure — it moves the same frames off the call stack, which is usually the entire point.

All 194 stack LeetCode problems

Every problem in the library the stack pattern applies to, grouped by LeetCode's own difficulty rating. 154 of the 194 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Stack pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.