Stack Interview Patterns: Parentheses, Calculator, Histogram & More
Beyond the monotonic stack, there are several classic stack patterns that appear repeatedly in coding interviews. The stack’s LIFO property shines for matching/nesting problems, expression evaluation, and maintaining previous-state context.
Why Use a Stack?
- Matching open/close brackets, tags, or parentheses
- Evaluating expressions (infix, postfix/RPN)
- Tracking the “most recent unseen” item (monotonic patterns)
- Converting recursion to iteration (DFS, backtracking)
- Implementing undo/redo or browser history
Pattern 1: Valid Parentheses / Bracket Matching
def is_valid(s):
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in mapping:
top = stack.pop() if stack else '#'
if mapping[ch] != top:
return False
else:
stack.append(ch)
return not stack
# Minimum add to make parentheses valid
def min_add_to_make_valid(s):
open_count = close_needed = 0
for ch in s:
if ch == '(':
open_count += 1
elif open_count > 0:
open_count -= 1
else:
close_needed += 1
return open_count + close_needed
Pattern 2: Basic Calculator (Expression Evaluation)
# Calculator I: handles +, -, and parentheses
def calculate(s):
stack = []
result = 0
sign = 1
i = 0
while i < len(s):
ch = s[i]
if ch.isdigit():
num = 0
while i < len(s) and s[i].isdigit():
num = num * 10 + int(s[i])
i += 1
result += sign * num
continue
elif ch == '+':
sign = 1
elif ch == '-':
sign = -1
elif ch == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif ch == ')':
result = stack.pop() * result + stack.pop()
i += 1
return result
# RPN / Postfix evaluation
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]
Pattern 3: Largest Rectangle in Histogram
Classic stack problem: for each bar, find the width of the largest rectangle it can be the shortest bar in. Maintain a stack of increasing heights; pop when you find a shorter bar.
def largest_rectangle(heights):
stack = [] # indices of increasing heights
max_area = 0
heights.append(0) # sentinel to flush remaining stack
for i, h in enumerate(heights):
start = i
while stack and heights[stack[-1]] >= h:
idx = stack.pop()
width = i - (stack[-1] + 1 if stack else 0)
max_area = max(max_area, heights[idx] * width)
start = idx
stack.append(start)
return max_area
Pattern 4: Daily Temperatures (Next Greater Element)
Monotonic stack: maintain a decreasing stack of indices. When a warmer day is found, pop and record the wait.
def daily_temperatures(T):
result = [0] * len(T)
stack = [] # indices, T values decreasing
for i, temp in enumerate(T):
while stack and T[stack[-1]] < temp:
idx = stack.pop()
result[idx] = i - idx
stack.append(i)
return result
# Next Greater Element II (circular array)
def next_greater_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
result[stack.pop()] = nums[i % n]
if i < n:
stack.append(i)
return result
Pattern 5: Decode String
Use stack to handle nested encoding like “3[a2[bc]]”:
def decode_string(s):
stack = []
cur_str = ""
cur_num = 0
for ch in s:
if ch.isdigit():
cur_num = cur_num * 10 + int(ch)
elif ch == '[':
stack.append((cur_str, cur_num))
cur_str = ""
cur_num = 0
elif ch == ']':
prev_str, num = stack.pop()
cur_str = prev_str + num * cur_str
else:
cur_str += ch
return cur_str
Classic Stack Interview Problems
| Problem | Key Stack Use | Complexity |
|---|---|---|
| Valid Parentheses | Match open/close pairs | O(n) |
| Basic Calculator I/II | Track partial sums + signs | O(n) |
| Evaluate Reverse Polish Notation | Operand stack | O(n) |
| Largest Rectangle in Histogram | Monotonic increasing | O(n) |
| Daily Temperatures | Monotonic decreasing | O(n) |
| Min Stack | Auxiliary min-tracking stack | O(1) all ops |
| Decode String | Nested context tracking | O(n) |
| Asteroid Collision | Simulate pairwise collisions | O(n) |
Min Stack — O(1) getMin()
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
min_val = min(val, self.min_stack[-1] if self.min_stack else val)
self.min_stack.append(min_val)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you solve the Valid Parentheses problem using a stack?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Iterate through the string. For every open bracket push it. For every close bracket, pop from the stack and check if it matches the corresponding open bracket (using a hash map: ) → (, ] → [, } → {). If the stack is empty on a close bracket or the popped bracket doesn't match, return False. After processing all characters, return True only if the stack is empty (all opens were matched).” }
},
{
“@type”: “Question”,
“name”: “What is the Min Stack problem and how do you achieve O(1) getMin()?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Min Stack supports push, pop, top, and getMin—all in O(1) time. Maintain two stacks: the main stack and a parallel min-stack where each entry is the minimum value seen so far at that depth. On push(val), push min(val, min_stack.top()) to the min-stack. On pop, pop from both stacks. getMin() returns min_stack.top(). No sorting or scanning needed—the min is always the top of the auxiliary stack.” }
},
{
“@type”: “Question”,
“name”: “How does the Largest Rectangle in Histogram algorithm work?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Maintain a monotonic increasing stack of bar indices. For each bar: while the stack top is taller than or equal to the current bar, pop it and compute the area it could span—the width extends from the new stack top+1 to the current index. The current bar acts as the right boundary, the stack top after popping as the left boundary. Append a sentinel bar of height 0 at the end to flush the entire stack. Time O(n), space O(n).” }
}
]
}