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.
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.
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 forstack.top(). Pop it, record the answer.Keep popping while the condition holds.
Push
ionto the stack.
At the end, anything remaining in the stack has no next greater → answer stays -1.
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]:
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.
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.
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
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]:
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.
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.
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]:
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:
Open brackets must be closed by the same type.
Open brackets must be closed in the correct order.
"()" → true
"()[]{}" → true
"(]" → false
"([)]" → false
"{[]}" → true
Solution:
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 "{[]}":
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 "([)]":
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.
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)
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 "()))((":
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):
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.
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.
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:
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.
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:
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
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:
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
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:
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:
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.
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:
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:
LeetCode 496 — Next Greater Element I
LeetCode 739 — Daily Temperatures
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:
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
conditionis (greater/smaller)What
record_answerdoes (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.
