Monotonic Stack
Learn the monotonic stack pattern for solving next greater element, daily temperatures, and similar problems in O(n).
Monotonic Stack
A monotonic stack is a stack that maintains its elements in either strictly increasing or strictly decreasing order. Whenever a new element would break that order, elements are popped until the order is restored. This pattern solves an entire category of "next greater/smaller element" problems in O(n) instead of O(n²).
The problem it solves
Problem: For each element in an array, find the next element to its right that is greater than it. If none exists, use -1.
Input: [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, -1]
index 0: 2 → next greater is 4 (at index 3)
index 1: 1 → next greater is 2 (at index 2)
index 2: 2 → next greater is 4 (at index 3)
index 3: 4 → nothing greater to the right → -1
index 4: 3 → nothing greater to the right → -1Brute force — O(n²): For each element, scan everything to its right.
Monotonic stack — O(n): Each element is pushed once and popped at most once — total work is O(n).
Input array
How it works
def next_greater_element(arr):
n = len(arr)
result = [-1] * n
stack = [] # stores indices, kept in decreasing value order
for i in range(n):
# current element might be the "next greater" for elements in stack
while stack and arr[stack[-1]] < arr[i]:
idx = stack.pop()
result[idx] = arr[i]
stack.append(i)
return result
arr = [2, 1, 2, 4, 3]
print(next_greater_element(arr)) # [4, 2, 4, -1, -1]Why this works: The stack holds indices of elements still "waiting" for their next greater element. When a bigger element arrives, it resolves every smaller element still on the stack — they all just found their answer.
Trace through the example
arr = [2, 1, 2, 4, 3]
i=0, arr[0]=2: stack empty → push 0. stack=[0]
i=1, arr[1]=1: 1 < arr[0]=2, no pop → push 1. stack=[0,1]
i=2, arr[2]=2: 2 > arr[1]=1 → pop 1, result[1]=2
2 == arr[0]=2, not strictly greater → stop popping
push 2. stack=[0,2]
i=3, arr[3]=4: 4 > arr[2]=2 → pop 2, result[2]=4
4 > arr[0]=2 → pop 0, result[0]=4
stack empty → push 3. stack=[3]
i=4, arr[4]=3: 3 < arr[3]=4, no pop → push 4. stack=[3,4]
End: indices 3 and 4 remain on stack — no greater element exists
result = [4, 2, 4, -1, -1]Classic problem — daily temperatures
Problem: Given daily temperatures, find how many days you must wait for a warmer day.
def daily_temperatures(temps):
n = len(temps)
result = [0] * n
stack = [] # indices of days waiting for a warmer day
for i in range(n):
while stack and temps[stack[-1]] < temps[i]:
prev_day = stack.pop()
result[prev_day] = i - prev_day # how many days waited
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Day 0 (73°) waits 1 day for day 1 (74°). Day 2 (75°) waits 4 days for day 6 (76°). Day 6 and 7 never get warmer — 0 days.
Classic problem — largest rectangle in histogram
A harder variant — for each bar, find how far it can extend left and right while staying the shortest bar in that range.
def largest_rectangle(heights):
stack = [] # indices, heights in increasing order
max_area = 0
heights = heights + [0] # sentinel to flush the stack at the end
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle(heights)) # 10When to use monotonic stack
| Signal in the problem | Use monotonic stack |
|---|---|
| "Next greater element" | Yes |
| "Next smaller element" | Yes |
| "Days until warmer/colder" | Yes |
| "Largest rectangle" | Yes |
| Need to compare each element against unresolved previous ones | Yes |
| Order does not matter, just existence | No — use a regular set |
The key signal — the problem asks about the next element satisfying some comparison, looking forward from each position. Whenever you see "next greater," "next smaller," or "how many days until," reach for a monotonic stack.
Complexity
| Time | Space | |
|---|---|---|
| Monotonic stack | O(n) | O(n) |
| Brute force (nested loop) | O(n²) | O(1) |
Each element is pushed exactly once and popped at most once — giving O(n) total operations even though there is a nested-looking while loop inside the for loop.