All patterns
Monotonic Stack
Keep candidates in order so each element resolves its answer once.
time O(n)space O(n)
What it is
Maintain a stack whose values are monotone. When a new element breaks the order, pop and resolve the popped ones. Every element is pushed and popped once, so the total is O(n).
When to reach for it
- Next greater or smaller element
- Span, temperature or histogram problems
- Matching nested structure
Clues in the problem
- For each i, look right or left for the first element that is bigger or smaller
- Brute force is an inner loop that scans forward
Template
def next_greater(a):res = [-1] * len(a)st = [] # indices, values decreasingfor i, x in enumerate(a):while st and a[st[-1]] < x:res[st.pop()] = xst.append(i)return res
Practice problems
- Daily Temperatures
- Next Greater Element
- Largest Rectangle in Histogram
- Trapping Rain Water
Common mistakes
- Storing values when you need indices
- Wrong comparison direction (strict vs non-strict) with duplicates
- Forgetting to drain the stack at the end when needed