Pattern 05 of 22
Stack Pattern: Template + 194 LeetCode Problems
When the most recent unresolved thing is the one that matters, use a stack.
- Easy
- 26
- Medium
- 107
- Hard
- 61
- Time
- O(n)
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 unbalancedComplexity 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.
Eyes only
Meet the stack problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
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.
Easy (26)
Medium (107)
Hard (61)
Stack pattern FAQ
What is the stack pattern?
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.
How many LeetCode problems use the stack pattern?
This page lists 194 LeetCode problems that the stack pattern applies to: 26 Easy, 107 Medium and 61 Hard. 154 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the stack pattern?
O(n) time and O(n) space. 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.
When should I use the stack pattern in an interview?
The input nests: brackets, tags, paths, expressions, nested encodings. A new element resolves against the most recent unmatched one rather than the oldest.
Which stack problem should I start with?
LeetCode 20. Valid Parentheses is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to stack?
Monotonic Stack, Tree Traversal, Depth-First Search, Linked List. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.