Core Idea
A stack (LIFO) is the right tool when the most recently seen element determines the action for the current element. The key intuition: a stack lets you look “back” efficiently at previous elements without rescanning. Most stack patterns run in O(n) amortized — each element is pushed and popped at most once.
Monotonic Stack (Next Greater Element)
Maintain a stack of indices in decreasing order of values. For each element, pop all elements smaller than the current one — the current element is the “next greater” for each popped element.
def next_greater(nums):
result = [-1] * len(nums)
stack = [] # indices of unresolved elements
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val # val is the next greater for nums[j]
stack.append(i)
return result
LC 496 (Next Greater Element I), LC 739 (Daily Temperatures — next warmer day), LC 503 (circular array: iterate 2n, index with i%n).
Largest Rectangle in Histogram (LC 84)
Maintain a monotonically increasing stack of indices. When a bar shorter than the top is encountered, pop and compute the rectangle width using the current index and the new top of stack.
def largestRectangleArea(heights):
heights.append(0) # sentinel to flush all remaining
stack = [-1] # sentinel for left boundary
max_area = 0
for i, h in enumerate(heights):
while stack[-1] != -1 and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
LC 85 (Maximal Rectangle): apply LC 84 on each row of a binary matrix treating column heights as the histogram.
Valid Parentheses and Matching
Push opening brackets; on closing bracket, check if top matches. Standard: LC 20. Extended: LC 1249 (Minimum Remove to Make Valid), LC 1963 (min swaps). For counting min additions: maintain open_count (unmatched opens) and close_count (unmatched closes). Scan left to right: ‘)’ with open_count=0 increments close_count; ‘)’ with open_count>0 decrements open_count; ‘(‘ increments open_count. Answer = open_count + close_count.
def minAddToMakeValid(s):
open_count = close_count = 0
for c in s:
if c == '(':
open_count += 1
elif open_count > 0:
open_count -= 1
else:
close_count += 1
return open_count + close_count
Min Stack (LC 155)
Maintain a second stack tracking the running minimum. On push: push min(val, min_stack.top()) to min_stack. On pop: pop from both stacks. getMin() = min_stack.top(). O(1) for all operations.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
m = val if not self.min_stack else min(val, self.min_stack[-1])
self.min_stack.append(m)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def getMin(self):
return self.min_stack[-1]
Evaluate Expression / Calculator
LC 224/227/772 (Basic Calculator series). Key insight for handling operator precedence: when you see ‘+’ or ‘-‘, push the current result onto the stack along with the sign. When you see ‘(‘, push the running result and sign onto the stack and reset. When you see ‘)’, pop and combine.
def calculate(s):
stack = []
num = 0
sign = 1
result = 0
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c in '+-':
result += sign * num
num = 0
sign = 1 if c == '+' else -1
elif c == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif c == ')':
result += sign * num
num = 0
result *= stack.pop() # sign before (
result += stack.pop() # result before (
return result + sign * num
When to Use a Stack
- Matching pairs: parentheses, brackets, tags
- “Next greater/smaller” element: monotonic stack
- Largest rectangle / maximal area: histogram problems
- Undo/redo operations, expression evaluation
- DFS iterative implementation
- Any pattern where the current element interacts with the most recent unresolved element
Meta coding interviews frequently test stack and monotonic stack patterns. See common questions for Meta interview: stack and monotonic stack problems.
Amazon coding interviews test stack patterns and expression evaluation. Review problems for Amazon interview: stack and expression evaluation problems.
Atlassian coding rounds include stack and parentheses problems. See patterns for Atlassian interview: stack and bracket matching problems.