Stacks & Monotonic Stacks
LIFO thinking for matching, parsing, and the monotonic-stack pattern that solves 'next greater element' in one pass.
A stack gives you one rule: the last thing in is the first thing out. That sounds small, but it matches a surprising number of problems: nested parentheses, parser state, undo history, recursion simulation, and “the nearest thing before me that still matters.”
The monotonic stack is the interview workhorse. You keep the stack ordered — increasing or decreasing — and pop items the moment the current value proves their answer. This turns next-greater and next-smaller questions from nested search into one pass.
The mental model
In Python, a list is a perfect stack when you use only the right end:
stack = []
stack.append("(")
stack.append("[")
top = stack.pop() # "["For matching problems, the stack stores unfinished openings. For monotonic problems, it stores unresolved candidates, usually indices rather than values so you can compute distances.
def next_greater(nums):
ans = [-1] * len(nums)
stack = [] # indices with decreasing values
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
j = stack.pop()
ans[j] = x
stack.append(i)
return ansEvery index is pushed once and popped at most once. The while loop looks nested, but across the whole run it performs O(n) pops.
Pattern recognition
Variations
Worked problems
The first problem is pure LIFO. The next two are monotonic stacks: each index waits until a future value resolves it.
Valid Parentheses
Given a string containing bracket characters, decide whether every opening bracket is closed by the same type of bracket and in the correct nested order.
Approach. Push opening brackets. When a closing bracket appears, the most recent unmatched opener must be its partner. If the stack is empty or the type does not match, the string is invalid. At the end, no openers may remain.
Show solution
def is_valid(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in pairs.values():
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stackComplexity. O(n) time, O(n) space in the worst case when every character is an opening bracket.
Daily Temperatures
For each day’s temperature, report how many days you must wait until a warmer temperature appears. If no warmer day exists, leave 0 for that day.
Approach. Keep a decreasing stack of day indices whose warmer day has not been found. When today’s temperature is higher than the temperature at the stack top, today resolves that older day.
Show solution
def daily_temperatures(temperatures):
waits = [0] * len(temperatures)
stack = []
for today, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev = stack.pop()
waits[prev] = today - prev
stack.append(today)
return waitsComplexity. O(n) time, O(n) space. Each day is pushed once and popped at most once.
Largest Rectangle in Histogram
Given bar heights in a histogram, find the area of the largest rectangle that can be formed using adjacent bars.
Approach. For a bar to be the limiting height of a rectangle, you need to know how far it can extend before a shorter bar stops it. Maintain an increasing stack of indices. When a shorter height arrives, pop taller bars and compute the widest rectangle where each popped bar is the minimum height. A final sentinel height flushes the stack.
Show solution
def largest_rectangle_area(heights):
best = 0
stack = []
for i, height in enumerate(heights + [0]):
while stack and heights[stack[-1]] > height:
h = heights[stack.pop()]
left_boundary = stack[-1] if stack else -1
width = i - left_boundary - 1
best = max(best, h * width)
stack.append(i)
return bestComplexity. O(n) time, O(n) space. The sentinel creates one extra iteration; each real bar still enters and leaves the stack once.
The classic pitfall
When a problem says “nearest” or “next,” ask what information becomes known the instant a later value breaks the stack’s order. That is the answer you compute on pop.