# Monotonic Stack: The Complete Pattern Guide What is a Monotonic Stack? A **monotonic stack** is a regular stack with one rule: elements inside it are always in a consistent order — either strictly increasing or strictly decreasing from bottom to top. * **Monotonic Increasing Stack** → each new element is ≥ the top. Bottom is smallest, top is largest. * **Monotonic Decreasing Stack** → each new element is ≤ the top. Bottom is largest, top is smallest. The magic: when you push a new element and it *violates* the order, you **pop** everything that violates it first. Those pops are where the answers come from. **When to reach for this pattern:** * You need the *next/previous greater/smaller* element for every index. * You're computing spans, widths, or ranges where an element is dominant. * The naive O(n²) approach is: for each element, scan left/right for something bigger/smaller. The monotonic stack collapses that into **O(n)** — every element is pushed and popped at most once. * * * ## Part 1: Next Greater Element ### Problem Statement Given an array, for each element find the first element to its **right** that is strictly greater. If none exists, answer is -1. ```plaintext Input: [2, 1, 3, 4, 1] Output: [3, 3, 4,-1,-1] ``` Let's verify manually: * 2 → first greater to right = 3 ✓ * 1 → first greater to right = 3 ✓ * 3 → first greater to right = 4 ✓ * 4 → nothing greater → -1 ✓ * 1 → nothing greater → -1 ✓ ### Naive Solution (O(n²)) For each index i, scan everything to its right. ```python def next_greater_naive(arr): n = len(arr) result = [-1] * n for i in range(n): for j in range(i + 1, n): if arr[j] > arr[i]: result[i] = arr[j] break return result ``` Fine for small inputs. Terrible at n = 10^5. ### Monotonic Stack Solution (O(n)) **Key insight:** Walk left to right. Maintain a stack of *indices whose next greater element we haven't found yet*. The stack will always hold indices in *decreasing value order* (a decreasing monotonic stack). When we reach a new element `arr[i]`: * If `arr[i] > arr[stack.top()]` → the current element IS the next greater for `stack.top()`. Pop it, record the answer. * Keep popping while the condition holds. * Push `i` onto the stack. At the end, anything remaining in the stack has no next greater → answer stays -1. ```python def next_greater(arr): n = len(arr) result = [-1] * n stack = [] # stores indices for i in range(n): # current element breaks the decreasing order while stack and arr[i] > arr[stack[-1]]: idx = stack.pop() result[idx] = arr[i] stack.append(i) return result ``` **Trace through** `[2, 1, 3, 4, 1]`**:** ```plaintext i=0, arr[0]=2: stack empty → push 0. stack=[0] i=1, arr[1]=1: 1 < 2, no pop → push 1. stack=[0,1] i=2, arr[2]=3: 3 > arr[1]=1 → pop 1, result[1]=3 3 > arr[0]=2 → pop 0, result[0]=3 push 2. stack=[2] i=3, arr[3]=4: 4 > arr[2]=3 → pop 2, result[2]=4 push 3. stack=[3] i=4, arr[4]=1: 1 < arr[3]=4, no pop → push 4. stack=[3,4] Remaining in stack: [3,4] → result[3]=result[4]=-1 Final: [3, 3, 4, -1, -1] ✓ ``` ### Circular Variant (LeetCode 503) The array is circular — you can wrap around. Trick: simulate the circular nature by running two passes (loop up to `2n`) and use `% n` for index. ```python def next_greater_circular(nums): n = len(nums) result = [-1] * n stack = [] for i in range(2 * n): while stack and nums[i % n] > nums[stack[-1]]: idx = stack.pop() result[idx] = nums[i % n] if i < n: stack.append(i) return result ``` Only push real indices (i < n). The second pass just resolves remaining stack entries. * * * ## Part 2: Daily Temperatures ### Problem Statement (LeetCode 739) Given an array `temperatures`, return an array `answer` where `answer[i]` is the number of days you have to wait after day `i` to get a warmer temperature. If no such day exists, `answer[i] = 0`. ```plaintext Input: [73, 74, 75, 71, 69, 72, 76, 73] Output: [1, 1, 4, 2, 1, 1, 0, 0] ``` This is **Next Greater Element** with a twist: instead of storing the value, store the *distance* (index difference). ### Solution ```python def daily_temperatures(temperatures): n = len(temperatures) answer = [0] * n stack = [] # stores indices for i in range(n): while stack and temperatures[i] > temperatures[stack[-1]]: idx = stack.pop() answer[idx] = i - idx # distance between days stack.append(i) return answer ``` **Trace through** `[73, 74, 75, 71, 69, 72, 76, 73]`**:** ```plaintext i=0 (73): stack empty → push 0. stack=[0] i=1 (74): 74>73 → pop 0, ans[0]=1-0=1 push 1. stack=[1] i=2 (75): 75>74 → pop 1, ans[1]=2-1=1 push 2. stack=[2] i=3 (71): 71<75, push 3. stack=[2,3] i=4 (69): 69<71, push 4. stack=[2,3,4] i=5 (72): 72>69 → pop 4, ans[4]=5-4=1 72>71 → pop 3, ans[3]=5-3=2 72<75, push 5. stack=[2,5] i=6 (76): 76>72 → pop 5, ans[5]=6-5=1 76>75 → pop 2, ans[2]=6-2=4 push 6. stack=[6] i=7 (73): 73<76, push 7. stack=[6,7] Remaining [6,7] → ans[6]=ans[7]=0 Final: [1,1,4,2,1,1,0,0] ✓ ``` **Time:** O(n). Each index pushed and popped once. **Space:** O(n) for the stack. * * * ## Part 3: Largest Rectangle in Histogram This is the hardest problem in this set. Master this and you've mastered monotonic stacks. ### Problem Statement (LeetCode 84) Given an array `heights` representing a histogram (each bar has width 1), find the area of the largest rectangle that can be formed. ```plaintext Input: [2, 1, 5, 6, 2, 3] Output: 10 ``` The rectangle of area 10 comes from bars at index 2 and 3 (heights 5 and 6), width = 2, area = 5 × 2 = 10. ### Key Insight For each bar `i`, ask: *what is the largest rectangle where bar* `i` *is the shortest bar?* If bar `i` is the bottleneck, the rectangle can extend: * **Left**: as long as bars are ≥ `heights[i]` * **Right**: as long as bars are ≥ `heights[i]` So for each bar we need: * **Previous Smaller Element (PSE)**: first index to the left where height < `heights[i]` * **Next Smaller Element (NSE)**: first index to the right where height < `heights[i]` Width = `NSE - PSE - 1` Area = `heights[i] × width` ### Solution: Monotonic Increasing Stack We maintain an **increasing** stack. When a bar shorter than the top arrives, we've found the NSE for the top. ```python def largest_rectangle(heights): n = len(heights) stack = [] # stores indices, increasing by height max_area = 0 for i in range(n + 1): # sentinel: process remaining stack at the end curr_height = heights[i] if i < n else 0 while stack and curr_height < heights[stack[-1]]: h = heights[stack.pop()] # left boundary: new stack top (or -1 if empty) left = stack[-1] if stack else -1 width = i - left - 1 max_area = max(max_area, h * width) stack.append(i) return max_area ``` **Trace through** `[2, 1, 5, 6, 2, 3]`**:** ```plaintext i=0 (h=2): stack empty → push 0. stack=[0] i=1 (h=1): 1 < heights[0]=2 pop 0 (h=2), left=-1, width=1-(-1)-1=1, area=2 push 1. stack=[1] i=2 (h=5): 5 > 1 → push 2. stack=[1,2] i=3 (h=6): 6 > 5 → push 3. stack=[1,2,3] i=4 (h=2): 2 < heights[3]=6 pop 3 (h=6), left=2, width=4-2-1=1, area=6 2 < heights[2]=5 pop 2 (h=5), left=1, width=4-1-1=2, area=10 ← MAX 2 > heights[1]=1 → stop. push 4. stack=[1,4] i=5 (h=3): 3 > 2 → push 5. stack=[1,4,5] i=6 (sentinel h=0): 0 < heights[5]=3 pop 5 (h=3), left=4, width=6-4-1=1, area=3 0 < heights[4]=2 pop 4 (h=2), left=1, width=6-1-1=4, area=8 0 < heights[1]=1 pop 1 (h=1), left=-1, width=6-(-1)-1=6, area=6 max_area = 10 ✓ ``` **Why the sentinel (appending 0 at the end)?** Without it, anything remaining in the stack at the end needs a separate loop. The sentinel forces everything to be popped cleanly. **Time:** O(n). **Space:** O(n). * * * ## Part 4: Valid Parentheses → Min Add to Make Valid This section covers two related problems that use a stack (not strictly monotonic, but built on the same "unmatched element" tracking idea). ### Problem 4a: Valid Parentheses (LeetCode 20) Given a string containing `()`, `[]`, `{}`, determine if it's valid. Rules: 1. Open brackets must be closed by the same type. 2. Open brackets must be closed in the correct order. ```plaintext "()" → true "()[]{}" → true "(]" → false "([)]" → false "{[]}" → true ``` **Solution:** ```python def is_valid(s): stack = [] mapping = {')': '(', ']': '[', '}': '{'} for ch in s: if ch in mapping: # it's a closing bracket top = stack.pop() if stack else '#' if mapping[ch] != top: return False else: stack.append(ch) # it's an opening bracket return len(stack) == 0 ``` **Trace through** `"{[]}":` ```plaintext ch='{': push '{' stack=['{'] ch='[': push '[' stack=['{','['] ch=']': closing, top='[', mapping[']']='[' → match, pop stack=['{'] ch='}': closing, top='{', mapping['}']='{' → match, pop stack=[] stack empty → True ✓ ``` **Trace through** `"([)]"`**:** ```plaintext ch='(': push '(' stack=['('] ch='[': push '[' stack=['(','['] ch=')': closing, top='[', mapping[')']='(' → MISMATCH → False ✓ ``` **Time:** O(n). **Space:** O(n). * * * ### Problem 4b: Minimum Add to Make Parentheses Valid (LeetCode 921) Given a string of `(` and `)` that may be invalid, return the minimum number of bracket additions to make it valid. ```plaintext Input: "())" Output: 1 (need one '(' at the start) Input: "(((" Output: 3 (need three ')') Input: "()()" Output: 0 Input: "()))((" Output: 4 ``` **Key insight:** Track two counters: * `open`: unmatched `(` seen so far (need a `)` to close) * `close`: unmatched `)` seen so far (need a `(` before them) ```python def min_add_to_make_valid(s): open_count = 0 # unmatched '(' close_count = 0 # unmatched ')' for ch in s: if ch == '(': open_count += 1 else: # ch == ')' if open_count > 0: open_count -= 1 # matched this ')' with a previous '(' else: close_count += 1 # unmatched ')', needs a '(' before it return open_count + close_count ``` **Trace through** `"()))((":` ```plaintext ch='(': open=1, close=0 ch=')': open>0 → open=0, close=0 ch=')': open=0 → close=1 ch=')': open=0 → close=2 ch='(': open=1, close=2 ch='(': open=2, close=2 Result: open+close = 2+2 = 4 ✓ ``` **Alternative stack approach (cleaner mental model):** ```python def min_add_stack(s): stack = [] for ch in s: if ch == '(': stack.append('(') else: if stack and stack[-1] == '(': stack.pop() # matched pair else: stack.append(')') # unmatched ')' return len(stack) ``` Whatever remains in the stack is unmatched — each needs one addition. * * * ### Problem 4c: Minimum Add to Make Valid — Extended (LeetCode 1541) Now with `(` and `)` only, but the string can have multiple consecutive levels of nesting. Same idea, same counter approach. **Minimum Remove to Make Valid (LeetCode 1249):** Return one valid string (not the count). Use a stack to track indices of unmatched brackets, then remove those characters. ```python def min_remove_to_make_valid(s): stack = [] # indices of unmatched '(' to_remove = set() for i, ch in enumerate(s): if ch == '(': stack.append(i) elif ch == ')': if stack: stack.pop() # matched else: to_remove.add(i) # unmatched ')' to_remove |= set(stack) # unmatched '(' indices return ''.join(ch for i, ch in enumerate(s) if i not in to_remove) ``` * * * ## Part 5: Design Problems — Min Stack ### Problem Statement (LeetCode 155) Design a stack that supports: * `push(val)` * `pop()` * `top()` * `getMin()` — retrieves the minimum element in **O(1)** The challenge: `getMin()` must be O(1), not O(n). ### Approach 1: Auxiliary Stack Maintain a second stack `min_stack` that always stores the current minimum. ```python class MinStack: def __init__(self): self.stack = [] self.min_stack = [] # top = current minimum def push(self, val): self.stack.append(val) # push to min_stack if it's the new minimum (or min_stack is empty) if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self): val = self.stack.pop() if val == self.min_stack[-1]: self.min_stack.pop() def top(self): return self.stack[-1] def getMin(self): return self.min_stack[-1] ``` **Trace:** ```plaintext push(5): stack=[5], min_stack=[5] push(3): stack=[5,3], min_stack=[5,3] push(7): stack=[5,3,7], min_stack=[5,3] ← 7 > 3, don't push push(3): stack=[5,3,7,3], min_stack=[5,3,3] ← 3 ≤ 3, push getMin() → 3 ✓ pop() → removes 3 from stack, 3==min_stack[-1] → pop from min_stack stack=[5,3,7], min_stack=[5,3] getMin() → 3 ✓ pop() → removes 7, 7 ≠ 3 → don't touch min_stack stack=[5,3], min_stack=[5,3] pop() → removes 3, 3==min_stack[-1] → pop stack=[5], min_stack=[5] getMin() → 5 ✓ ``` **Time:** O(1) for all operations. **Space:** O(n) worst case (all distinct decreasing values). ### Approach 2: Store (value, current\_min) Pairs Each stack element stores a tuple: the value AND the minimum at the time of pushing. ```python class MinStack: def __init__(self): self.stack = [] # stores (value, min_so_far) def push(self, val): current_min = min(val, self.stack[-1][1]) if self.stack else val self.stack.append((val, current_min)) def pop(self): self.stack.pop() def top(self): return self.stack[-1][0] def getMin(self): return self.stack[-1][1] ``` **Trace:** ```plaintext push(5): stack=[(5,5)] push(3): min(3,5)=3, stack=[(5,5),(3,3)] push(7): min(7,3)=3, stack=[(5,5),(3,3),(7,3)] push(2): min(2,3)=2, stack=[(5,5),(3,3),(7,3),(2,2)] getMin() → stack[-1][1] = 2 ✓ pop(): stack=[(5,5),(3,3),(7,3)] getMin() → 3 ✓ ``` This approach is slightly simpler to reason about and eliminates the need to sync two stacks. * * * ## Part 6: Design Problems — Max Stack ### Problem Statement (LeetCode 716) Design a stack that supports: * `push(val)` * `pop()` * `top()` * `peekMax()` — returns max element in O(1) * `popMax()` — removes and returns max element `popMax()` is the hard part. It must remove the **maximum element wherever it is** in the stack, not just the top. ### Approach: Two Stacks ```python class MaxStack: def __init__(self): self.stack = [] self.max_stack = [] # top = current max def push(self, val): self.stack.append(val) if not self.max_stack or val >= self.max_stack[-1]: self.max_stack.append(val) else: self.max_stack.append(self.max_stack[-1]) # repeat current max def pop(self): self.max_stack.pop() return self.stack.pop() def top(self): return self.stack[-1] def peekMax(self): return self.max_stack[-1] def popMax(self): max_val = self.peekMax() # Use a temp stack to find and remove max_val temp = [] while self.stack[-1] != max_val: temp.append(self.pop()) self.pop() # remove the max while temp: self.push(temp.pop()) return max_val ``` **Trace:** ```plaintext push(5): stack=[5], max_stack=[5] push(1): stack=[5,1], max_stack=[5,5] ← 1<5, repeat 5 push(5): stack=[5,1,5], max_stack=[5,5,5] push(3): stack=[5,1,5,3], max_stack=[5,5,5,5] peekMax() → 5 popMax(): max_val=5 top()=3 ≠ 5: pop 3, temp=[3] top()=5 == 5: pop it (the max) push temp back: push 3 Result stack=[5,1,3], max_stack=[5,5,5] returns 5 ``` **Complexity:** * `push`, `pop`, `top`, `peekMax` → O(1) * `popMax` → O(n) worst case (max is at the bottom) ### Optimized Approach: Doubly Linked List + TreeMap For a fully O(log n) `popMax`, use: * A **doubly linked list** (DLL) as the actual stack (O(1) deletion anywhere) * A **sorted map** (or heap) mapping value → list of DLL nodes ```python from sortedcontainers import SortedDict class MaxStack: def __init__(self): self.dll = [] # simulate as list of nodes for simplicity self.map = SortedDict() # val → [indices in dll] def push(self, val): idx = len(self.dll) self.dll.append(val) if val not in self.map: self.map[val] = [] self.map[val].append(idx) def pop(self): val = self.dll.pop() self.map[val].pop() if not self.map[val]: del self.map[val] return val def top(self): return self.dll[-1] def peekMax(self): return self.map.peaklast()[0] def popMax(self): max_val = self.map.peaklast()[0] idx = self.map[max_val].pop() if not self.map[max_val]: del self.map[max_val] self.dll[idx] = None # mark as deleted # rebuild stack without None while self.dll and self.dll[-1] is None: self.dll.pop() return max_val ``` In interviews, the two-stack approach is typically expected unless the interviewer explicitly asks for O(log n). The DLL + SortedDict approach impresses in senior-level discussions. * * * ## Pattern Recognition: How to Identify Monotonic Stack Problems Ask yourself these questions when you see an array problem: **1\. "For each element, find the nearest X"?** * Nearest greater to the right → decreasing stack * Nearest smaller to the right → increasing stack * Nearest greater to the left → process right to left, decreasing stack * Nearest smaller to the left → process right to left, increasing stack **2\. Does the problem involve spans, widths, or areas?** * Rectangle area problems → increasing stack (pop when you find something smaller) * Water trapping problems (Trapping Rain Water, LeetCode 42) → two-pointer or monotonic stack **3\. Is there a "dominant element" concept?** * Stock span, sliding window maximum → monotonic stack or deque **Quick reference table:** ```plaintext Problem Stack Type What Triggers a Pop -------------------------------------------------------------------- Next Greater Element Decreasing arr[i] > top Next Smaller Element Increasing arr[i] < top Previous Greater Element Decreasing (scan right to left) Previous Smaller Element Increasing (scan right to left) Largest Rectangle in Histogram Increasing arr[i] < top Daily Temperatures Decreasing temp[i] > top Trapping Rain Water Decreasing height[i] > top ``` * * * ## Common Mistakes and How to Avoid Them **1\. Storing values vs indices** Almost always store **indices** in the stack, not values. You can always get the value via `arr[idx]`, but you can't get the index back from a value. **2\. Off-by-one in width calculations** For Largest Rectangle: ```plaintext width = right_boundary - left_boundary - 1 ``` Where: * `right_boundary = i` (current index causing the pop) * `left_boundary = stack[-1]` after popping (or -1 if empty) The `-1` is because both boundaries are *exclusive*. **3\. Forgetting the sentinel** In histogram problems, the sentinel (appending 0) forces remaining elements to be processed. Without it you need an extra loop. Always add it. **4\. Min/Max Stack: the** `<=` **vs** `<` **edge case** For Min Stack's auxiliary stack, push when `val <= current_min` (not just `<`). If you use strict `<`, duplicate minimums won't be tracked correctly. ```plaintext push(3), push(3): Wrong (<): min_stack=[3] → pop once removes it, min is lost Correct (≤): min_stack=[3,3] → two pops needed, correct ``` **5\. Max Stack's popMax rebuild direction** When rebuilding after `popMax`: ```python while temp: self.push(temp.pop()) # pop from temp (LIFO) to restore order ``` Don't iterate forward through temp — that reverses the order. * * * ## Practice Problems (Recommended Order) **Warm-up:** 1. LeetCode 496 — Next Greater Element I 2. LeetCode 739 — Daily Temperatures 3. LeetCode 20 — Valid Parentheses **Core:** 4\. LeetCode 503 — Next Greater Element II (circular) 5\. LeetCode 901 — Online Stock Span 6\. LeetCode 921 — Min Add to Make Valid 7\. LeetCode 84 — Largest Rectangle in Histogram 8\. LeetCode 155 — Min Stack 9\. LeetCode 716 — Max Stack **Advanced:** 10\. LeetCode 85 — Maximal Rectangle 11\. LeetCode 42 — Trapping Rain Water 12\. LeetCode 1249 — Min Remove to Make String Valid 13\. LeetCode 907 — Sum of Subarray Minimums * * * ## Summary The monotonic stack is a **single pass, O(n) pattern** that answers "nearest greater/smaller" queries by maintaining a stack in sorted order and recording answers at pop-time. The core loop always looks like: ```python for i in range(n): while stack and condition(arr[i], arr[stack[-1]]): idx = stack.pop() record_answer(idx, i) # the answer for idx is i (or derived from both) stack.append(i) ``` The variation is in: * What `condition` is (greater/smaller) * What `record_answer` does (value, distance, area) * Whether you use a sentinel at the end For **design problems**, the key insight is pairing the main stack with an auxiliary structure (second stack, or sorted map) so that min/max queries remain O(1) or O(log n) — sacrificing space to preserve time complexity. Master this pattern and you'll handle ~15 LeetCode problems that appear regularly in FAANG interviews with the same 20 lines of code.