Stacks
Last In, First Out. Push when you encounter something, pop when you need to resolve it. The most recent thing is always at the top — that's the power of LIFO.
Find matching brackets with a scan — O(n²). Stack resolves them as they appear — O(n)
The insight: LIFO matches the structure of nested problems. The most recently opened bracket must be closed first. A stack naturally holds "the most recent unresolved thing" — push when you open something, pop when you close it.
Two Stack Uses
Every stack problem is one of these two uses.
Push items when encountered, pop to resolve or undo. Top of stack = most recent unresolved item.
Maintain stack in increasing or decreasing order. New element breaks the order → pop and resolve smaller elements. Each element pushed/popped at most once → O(n).
The 3-Step Framework
Three questions before every stack problem.
For matching: push the opening element. For monotonic: push indices (not values) so you can fill result[idx] when popping. For path: push directory names.
stack.append(ch) # matching: push opener
stack.append(i) # monotonic: push index
stack.append(part) # path: push dir nameFor matching: pop when closer matches top. For monotonic NGE: pop while stack[-1] < current. For path: pop on '..'.
if stack and stack[-1] == matching[ch]: stack.pop()
while stack and nums[stack[-1]] < nums[i]: result[stack.pop()] = nums[i]
if part == '..' and stack: stack.pop()Matching: len(stack)==0. Monotonic: remaining = no NGE, stay -1. Path: join stack. Most answers are built during pops, not after.
return len(stack) == 0 # matching
return result # NGE (filled during loop)
return '/' + '/'.join(stack) # pathPattern Recognition
Spot the stack before reaching for a loop.