9 drills · 9 pattern exercises · 11 micro drills
Patterns used in this topic, with difficulty breakdown.
Calculate the result of a math expression written in postfix notation like '2 1 + 3 *'.
All 9 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Check if every opening bracket has a matching closing bracket in the correct order.
A stack naturally models nesting: the most recent opening bracket must match the next closing bracket — LIFO order.
Prompt
Check if a string of brackets is balanced: ()[]{}
Solution
def is_balanced(s):
stack = []
pairs = {')':'(', ']':'[', '}':'{'}
for c in s:
if c in '([{':
stack.append(c)
# LIFO matches innermost first
elif c in pairs:
if not stack or stack.pop() != pairs[c]:
return False
return len(stack) == 0
# Test: is_balanced("{[()]}") == True
# Test: is_balanced("{[(])}") == FalseIn plain English: Build a first-in-first-out queue using only two last-in-first-out stacks.
Reversing a stack flips LIFO into FIFO — the lazy transfer (only when output is empty) makes this amortized O(1).
Prompt
Implement a FIFO queue using only two stacks.
Solution
class Queue:
def __init__(self):
self.sin = []
self.sout = []
def enqueue(self, x):
self.sin.append(x)
def dequeue(self):
if not self.sout:
# lazy transfer: only when needed
while self.sin:
self.sout.append(self.sin.pop())
return self.sout.pop()
# Test: q = Queue(); q.enqueue(1); q.enqueue(2); q.dequeue() == 1In plain English: Build a stack that also tells you the current minimum element in O(1) time.
Storing the running minimum alongside each value preserves the min history as elements are popped — no need to rescan.
Prompt
Design a stack that supports push, pop, and getMin in O(1).
Solution
class MinStack:
def __init__(self):
self.stack = [] # stores (val, cur_min)
def push(self, x):
cur_min = min(x, self.stack[-1][1]) if self.stack else x
self.stack.append((x, cur_min)) # pair: (value, min-so-far)
def pop(self):
return self.stack.pop()[0]
def get_min(self):
return self.stack[-1][1]
# Test: push(3), push(1), push(5) => get_min() == 1In plain English: Calculate the result of a math expression written in postfix notation like '2 1 + 3 *'.
Postfix notation eliminates the need for parentheses and precedence — operands are always ready on the stack when an operator appears.
Prompt
Evaluate a postfix (reverse Polish notation) expression.
Solution
def eval_postfix(tokens):
stack = []
ops = {'+': lambda a,b: a+b, '-': lambda a,b: a-b,
'*': lambda a,b: a*b, '/': lambda a,b: int(a/b)}
for t in tokens:
if t in ops:
b, a = stack.pop(), stack.pop() # pop order matters: b first, then a
stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]
# Test: eval_postfix(["2","1","+","3","*"]) == 9In plain English: For each number in an array, find the first larger number to its right.
A monotonic stack maintains elements in decreasing order — when a larger element arrives, it 'resolves' all smaller elements on the stack.
Prompt
For each element, find the next element to its right that is larger.
Solution
def next_greater(a):
res = [-1] * len(a)
stack = []
for i in range(len(a) - 1, -1, -1):
while stack and stack[-1] <= a[i]: # pop smaller elements: they found their answer
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(a[i])
return res
# Test: next_greater([4,5,2,25]) == [5,25,25,-1]In plain English: For each day, find how many days you have to wait until a warmer day comes.
Use a monotonic decreasing stack of indices. When a new temperature is higher than the stack top, pop and record the distance. Each element is pushed and popped at most once — O(n) total.
Prompt
Given an array of daily temperatures, return an array where each element says how many days until a warmer temperature. If none, put 0.
Solution
def daily_temperatures(temps):
n = len(temps)
result = [0] * n
stack = [] # monotonic decreasing stack of indices
for i in range(n):
while stack and temps[i] > temps[stack[-1]]:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
# Test: daily_temperatures([73,74,75,71,69,72,76,73])
# == [1,1,4,2,1,1,0,0]In plain English: Check if a string of parentheses is properly opened and closed.
Every open paren expects exactly one close paren — the stack tracks unmatched opens and must be empty at the end.
Prompt
Check if a string of parentheses () is valid.
Solution
def is_valid(s):
stack = [] # track unmatched open parens
for c in s:
if c == '(':
stack.append(c)
elif c == ')':
if not stack:
return False # no matching open
stack.pop()
return len(stack) == 0 # all opens must be matched
# Test: is_valid("(())()") == True
# Test: is_valid("(()") == FalseIn plain English: Reverse a string by pushing all characters onto a stack and popping them off.
LIFO order naturally reverses a sequence — push in order, pop gives reverse order.
Prompt
Reverse a string using a stack.
Solution
def reverse_string(s):
stack = list(s) # push all chars
result = []
while stack:
result.append(stack.pop()) # LIFO pops in reverse order
return ''.join(result)
# Test: reverse_string("hello") == "olleh" In plain English: Evaluate a math expression written in postfix notation using a stack.
Push numbers onto the stack. When you hit an operator, pop two operands, apply the operator, and push the result. The stack naturally handles operator precedence and nesting.
Prompt
Evaluate an expression in Reverse Polish Notation (postfix). Valid operators are +, -, *, /. Each operand is an integer.
Solution
def eval_rpn(tokens):
stack = []
ops = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: int(a / b), # truncate toward zero
}
for t in tokens:
if t in ops:
b, a = stack.pop(), stack.pop()
stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]
# Test: eval_rpn(["2","1","+","3","*"]) == 9 ((2+1)*3)
# Test: eval_rpn(["4","13","5","/","+"]) == 6 (4+(13/5))9 exercises: spot the signals, pick the method, avoid the trap.
Check if a string of brackets is balanced: ()[]{}
Signals
Push open brackets, pop on close brackets. Top must match. Stack empty at end → balanced. O(n).
Trap
Counter-based approach only works for single bracket type. Multiple types require a stack.
Implement a FIFO queue using only two stacks.
Signals
Push to inbox stack. On dequeue, transfer inbox → outbox (reversal). Amortized O(1) per operation.
Trap
Only transfer to outbox when outbox is empty — transferring every time is O(n) per dequeue.
Design a stack that supports push, pop, and getMin in O(1).
Signals
Store (value, current_min) pairs. On push, new_min = min(val, top.min). O(1) for all operations.
Trap
Tracking a single min variable breaks on pop — you lose the previous minimum.
Evaluate a postfix (reverse Polish notation) expression.
Signals
Push numbers. On operator, pop two, apply, push result. Final stack element is the answer. O(n).
Trap
Watch operand order for non-commutative ops: second_popped OP first_popped (e.g., subtraction).
For each element, find the next element to its right that is larger.
Signals
Maintain decreasing stack of indices. When a larger element arrives, it's the answer for all smaller stack elements. O(n).
Trap
Brute force nested loop is O(n²). The monotonic stack insight gives O(n) because each element is pushed/popped at most once.
Check if a string of parentheses () is valid.
Signals
Push '(' on open, pop on ')'. If stack empty when popping or non-empty at end → invalid. O(n).
Trap
A simple counter (increment on open, decrement on close) works here but doesn't extend to mixed bracket types.
Reverse a string using a stack.
Signals
Push each character, pop all into result. LIFO reverses the order. O(n).
In-place swap from both ends — more efficient (O(1) space) but the problem specifically asks for stack.
Trap
The problem constraints dictate the method here — 'using a stack' means use a stack.
Evaluate an arithmetic expression in Reverse Polish Notation (postfix).
Signals
Push numbers. On operator, pop two, compute, push result. O(n).
Trap
Division truncates toward zero in RPN. In Python, use int(a/b) not a//b (which floors).
Given daily temperatures, for each day find how many days until a warmer temperature.
Signals
Decreasing stack of indices. Pop while current temp > stack top. Distance = current - popped index. O(n).
Same approach. Each element pushed and popped at most once.
Trap
Don't scan forward from each day — that's O(n²). The monotonic stack makes it one pass.
11 quick recall drills to reinforce this topic.
Bracket matching is the classic stack application. Must be instant for interview warm-ups.
match = {'(': ')', '[': ']', '{': '}'}
stack = []
for c in s:
if c in match:
stack.append(match[c])
elif not stack or stack.pop() != c:
return False
return not stackStack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.
stack = []
stack.append(x)
stack.pop()Monotonic stacks find next-greater/smaller elements in O(n). Key for histogram and temperature problems.
stack = []
for x in a:
while stack and stack[-1] >= x:
stack.pop()
stack.append(x)Two-stack queue amortizes to O(1) per operation. Classic data structure design question.
in_stack, out_stack = [], []
def enqueue(x):
in_stack.append(x)
def dequeue():
if not out_stack:
while in_stack:
out_stack.append(in_stack.pop())
return out_stack.pop()Maintaining a parallel min stack gives O(1) getMin. Classic design problem.
self.stack.append(val)
self.min_stack.append(
min(val, self.min_stack[-1] if self.min_stack else val)
)Using a stack to reverse order is the intuition behind reversing linked lists and strings.
stack = []
for x in a:
stack.append(x)
reversed_a = []
while stack:
reversed_a.append(stack.pop())Stack-based expression evaluation is the foundation for calculator and RPN problems.
for tok in tokens:
if tok.lstrip('-').isdigit():
stack.append(int(tok))
else:
b, a = stack.pop(), stack.pop()
if tok == '+': stack.append(a + b)
elif tok == '-': stack.append(a - b)
elif tok == '*': stack.append(a * b)
elif tok == '/': stack.append(int(a / b))RPN evaluation: numbers push, operators pop two and push result. Note: pop order is b, a (right operand first).
stack = []
for tok in tokens:
if tok in '+-*/':
b, a = stack.pop(), stack.pop()
if tok == '+': stack.append(a + b)
elif tok == '-': stack.append(a - b)
elif tok == '*': stack.append(a * b)
else: stack.append(int(a / b))
else:
stack.append(int(tok))Next-greater-element uses a decreasing stack. Shows up in stock span and temperature problems.
result = [-1] * len(a)
stack = []
for i in range(len(a) - 1, -1, -1):
while stack and stack[-1] <= a[i]:
stack.pop()
if stack:
result[i] = stack[-1]
stack.append(a[i])Track open/close counts. Only add close paren when close < open.
def bt(o, c, cur):
if len(cur) == 2*n: res.append(cur); return
if o < n: bt(o+1, c, cur+'(')
if c < o: bt(o, c+1, cur+')')Decreasing stack resolves waiting days when a warmer temperature arrives.
res = [0] * len(t)
st = []
for i, v in enumerate(t):
while st and t[st[-1]] < v:
j = st.pop()
res[j] = i - j
st.append(i)