Cost
| Operation | Time | Space | Why |
|---|---|---|---|
| Push / pop / peek | O(1) | O(n) | An array with an index, or a linked list. Nothing is searched, so the operations are unconditionally constant. |
| Monotonic stack scan | O(n) | O(n) | A while loop inside a for loop, but each index is pushed once and popped once — at most 2n stack operations in total. |
| Bracket / expression matching | O(n) | O(n) | One push per opener, one pop per closer. Space is the nesting depth, which is n in the worst case. |
| Recursion converted to a stack | same | O(depth) | Turning recursion into an explicit stack does not change the cost, it moves the frames off the call stack and removes the overflow risk. |
Reach for it when
- Matching or nesting — brackets, tags, expression parsing, directory paths.
- "Next greater" or "previous smaller" for every element, in any disguise: daily temperatures, stock spans, largest rectangle in a histogram.
- Undo and history, or any "most recent thing first" behaviour.
- Converting a recursive traversal into an iterative one, when depth could blow the call stack.
- Evaluating or converting expressions — postfix evaluation is a stack and nothing else.
The plain version
Push, pop, peek, all O(1); the only access is the top. That restriction is the feature — it makes "the most recent unfinished thing" instantly available, which is what nesting problems need.
def is_balanced(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif not stack or stack.pop() != pairs[ch]:
return False
return not stack # leftovers mean unclosed openersTwo things in that function generalise to every stack problem: the guard before popping, and the check on what is left at the end.
The monotonic stack
Keep the stack sorted — increasing or decreasing — by popping anything that would break the order as each new element arrives. Each pop is then an answered question, which is the visualisation above.
def next_greater(nums):
out = [-1] * len(nums)
stack = [] # indices, values decreasing
for i, value in enumerate(nums):
while stack and nums[stack[-1]] < value:
out[stack.pop()] = value # this element is the answer
stack.append(i)
return outThe invariant is the part to say aloud: the stack holds the indices that have not yet found their next greater element, and their values decrease from bottom to top. Everything else follows. The new element resolves every waiting index smaller than it, then waits its own turn. Stopping at the first larger value is safe because everything below it is larger still.
Four decisions define a variant:
| Decision | Effect |
|---|---|
| Increasing or decreasing stack | Next greater versus next smaller |
| Scan left to right or right to left | Next versus previous |
< or <= in the pop test | Whether equal values resolve each other |
| Store indices or values | Whether widths and distances are computable |
Get those four right and the code is four lines.
Where the stack is hiding
Recursion is a stack — the call stack. Any recursive traversal can be rewritten with an explicit one, which is how iterative DFS works:
def dfs(root):
stack = [root]
while stack:
node = stack.pop()
visit(node)
stack.extend(reversed(node.children)) # reversed to keep left-to-right order
returnSwap that stack for a queue and the same six lines become breadth-first search. The container chooses the traversal order — which is the cleanest way to remember the difference.
What to say in the interview
Say what the stack holds before writing the loop, and if it is monotonic say why the ordering is maintained. Then give the cost with its justification: O(n) time because each element is pushed once and popped at most once, O(n) space for the stack. Nested loops with an amortized bound are a standard place to lose points by guessing O(n²).
Where candidates slip
- Storing values instead of indices in a monotonic stack. The moment the answer needs a position or a width — histogram rectangles, span lengths — values alone are not enough, and it is cheap to store indices from the start.
- Popping without checking the stack is empty. Every pop needs a guard, and a closing bracket with nothing to match is the test case that catches it.
- Forgetting what is left over. Items still on the stack at the end are not an error — they are the elements whose answer is "none", and they usually need an explicit default.
- Using the wrong comparison and silently changing the meaning.
<versus<=in the pop condition decides whether equal values resolve each other, which flips results for problems involving duplicates. - Claiming O(n²) for the monotonic scan because it has nested loops. The inner loop is bounded across the whole run, not per iteration — say the amortized argument out loud.