Stacks and Monotonic Stacks
On this page
A stack fits any problem where the most recent unfinished thing is the first one you can finish. Brackets are the classic case: the last bracket you opened is the first one that may close. A monotonic stack adds one rule, that values on the stack stay in sorted order, and it solves a whole family of "next greater / previous smaller" questions in one pass.
Stacks and Queues covers the data structure. This page covers the two patterns built on it.
When to recognise it
- Matching pairs and nesting: brackets, tags, "remove the minimum to make it valid", decode
3[a2[c]]. - Expression evaluation: calculators, "evaluate reverse Polish notation".
- "Next greater", "previous smaller", "how many days until warmer": for each element, find the nearest element on one side that beats it. That is a monotonic stack.
- Histogram and skyline areas: each bar's width is limited by the nearest shorter bar on each side.
- "Remove k digits to make the smallest number": a greedy rule implemented with an increasing stack.
Pattern 1: matching
Push openers. A closer must match the top of the stack, which is the most recent opener. At the end the stack must be empty.
def is_balanced(s):
"""Plain stack: push openers, every closer must match the top."""
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in '([{':
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack # leftover openers mean unbalanced
Time O(n), space O(n).
Pattern 2: monotonic stack
Walk left to right and keep indices of elements that are still waiting for their next greater element. When a new value x arrives, everything on top of the stack that is smaller than x has just found its answer: x. Pop them all, then push x. Values left on the stack are always decreasing, hence "monotonic".
![Walk-through for [2, 7, 3, 5, 4, 6, 8]: which elements each new value pops, and the stack after each step. 6 pops 4 and 5; 8 pops 6 and 7; 8 is left with no greater element.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-a013a4d5.png)
def next_greater(nums):
"""Monotonic stack (decreasing values): each index waits on the stack until a bigger value arrives."""
ans = [-1] * len(nums)
stack = [] # indices, their values strictly decreasing
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
ans[stack.pop()] = x # x is the answer for everything it pops
stack.append(i)
return ans
There is a nested while, but each index is pushed once and popped at most once, so the total is O(n).
The same loop answers "how many days until a warmer day" by storing the distance instead of the value:
def days_until_warmer(temps):
"""Same template, store the distance instead of the value."""
ans = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ans
Choosing the direction: for the next greater, keep values decreasing and pop smaller ones. For the next smaller, keep them increasing and pop larger ones. For previous instead of next, the answer is whatever is left on top of the stack just before you push.
Pattern 2b: both neighbours at once
In Largest Rectangle in Histogram, a bar's rectangle stretches until a shorter bar on each side. With an increasing stack, when a bar is popped, the bar that popped it is its right limit and the new top of the stack is its left limit.

def largest_rectangle(heights):
"""Increasing stack: when a bar is popped, the bar that popped it is its right limit,
and the new top of the stack is its left limit."""
stack = []
best = 0
for i, h in enumerate(heights + [0]): # sentinel 0 flushes the stack
while stack and heights[stack[-1]] >= h:
top = stack.pop()
left = stack[-1] if stack else -1
best = max(best, heights[top] * (i - left - 1))
stack.append(i)
return best
Common bugs
- Popping from an empty stack when a closer arrives first. Check
if not stackbeforepop(). - Forgetting the final check:
((passes the loop but is not balanced. - Storing values instead of indices. You usually need the index, for distances and widths. Store indices and read values through the array.
<vs<=when popping. For equal values, decide whether an equal element counts as "greater". The two choices give different answers on duplicates.- Leaving elements on the stack at the end. Either they mean "no answer" (−1, 0) or you need a sentinel to flush them, like the
0appended in the histogram code.
Say this in the interview
- "Each element waits on the stack until something bigger comes along. Every index is pushed once and popped once, so it's linear even with the inner while loop."
- "The stack holds indices, and the values at those indices are decreasing, so the top is always the nearest element that hasn't found its answer yet."
Problems for this pattern
- Valid Parentheses: matching.
- Min Stack: a second stack of minimums.
- Minimum Remove to Make Valid Parentheses: matching plus indices to drop.
- Evaluate Reverse Polish Notation: push numbers, pop two for each operator.
- Daily Temperatures: the monotonic template.
- Decode String: a stack of (string so far, repeat count).
- Basic Calculator II: a stack of signed terms.
- Largest Rectangle in Histogram: both neighbours from one stack.
- Simplify Path: push directory names, pop on "..".
Related
Stacks and Queues · Sliding Window (the monotonic deque for window maximums) · Tree DFS (iterative DFS uses a stack too)