PATTERN 6 OF 22

Stacks & Monotonic Stacks

Use LIFO ordering to match pairs, track state, and evaluate expressions. Monotonic stacks extend the idea to efficiently find the next greater or smaller element in O(n) time.

Time: O(n)

Space: O(n)

Learn & Reference

Understanding the Pattern

Stacks & Monotonic Stacks Pattern

A stack is a Last-In, First-Out (LIFO) data structure. You push items onto the top and pop them from the top. This simple property makes stacks surprisingly powerful for a whole class of problems.

Core Concept

Think of a stack of plates: you can only add or remove from the top. This constraint is exactly what you need when the most recent item is the most relevant — matching brackets, undoing operations, or evaluating expressions in reverse order.

Basic Stack Applications

1. Matching & Pairing

The most classic stack problem: check if brackets/parentheses are balanced. When you see an opening bracket, push it. When you see a closing bracket, pop and check if they match. If the stack is empty at the end, everything matched.

This extends to any problem where you need to match nested pairs — HTML tags, directory paths, or nested function calls.

2. State Tracking (Auxiliary Stack)

Sometimes you need O(1) access to a running property (like the current minimum) while still supporting push/pop. The trick is to maintain a second "auxiliary" stack that tracks the property in sync with the main stack.

For example, a Min Stack keeps a parallel stack where each entry is the minimum of all elements at or below that position. When you push, you also push the new minimum. When you pop, you pop from both stacks.

3. Expression Evaluation

Stacks are the natural data structure for evaluating postfix (Reverse Polish Notation) expressions, infix expressions with operator precedence, and building/evaluating expression trees.

The pattern: push operands. When you encounter an operator, pop the required operands, compute, and push the result back.

Monotonic Stacks

A monotonic stack maintains its elements in either increasing or decreasing order. When you try to push an element that would violate the order, you pop elements until the invariant is restored.

Why Monotonic Stacks Work

The key insight: when an element gets popped by a new element, the new element is the next greater (or smaller) element for everything being popped. This turns an O(n²) "for each element, scan right" approach into O(n) total, because each element is pushed and popped at most once.

4. Next Greater / Smaller Element

Given an array, find the next greater element for each position. Iterate left to right, maintaining a monotonically decreasing stack of indices:

For each new element, pop everything smaller — the new element is their "next greater"
Push the current index

This is the foundation of monotonic stack problems. Variations include next smaller element (use increasing stack), previous greater/smaller (iterate right to left), and circular arrays.

5. Histogram / Rectangle Problems

The "largest rectangle in histogram" is the definitive monotonic stack problem. For each bar, you need the nearest shorter bar on the left and right. A monotonically increasing stack of indices gives you both boundaries:

When a bar gets popped by a shorter bar, the popped bar's rectangle extends from the current stack top (left boundary) to the new bar (right boundary)

When Stacks Fail

The problem requires random access (use an array or hash map instead)
You need the minimum/maximum of a sliding window (use a monotonic deque, not a stack)
The pairing is not nested (e.g., regex matching may need backtracking, not a stack)
The ordering property is not monotonic (more complex data structures needed)

Common Mistakes

Not processing remaining stack elements: After iterating through the array, elements left in a monotonic stack have no "next greater/smaller" — you must handle them (usually set to -1 or 0)
Confusing increasing vs decreasing monotonic stack: A monotonically decreasing stack finds the next greater element. A monotonically increasing stack finds the next smaller element. This is counterintuitive
Storing values instead of indices: For most monotonic stack problems, store indices (not values) so you can compute distances or positions. You can always look up the value from the original array
Forgetting empty-stack checks: Always check if the stack is empty before peeking or popping — especially in bracket matching and monotonic stack problems
Off-by-one in histogram problems: When computing widths in the histogram problem, the width is current_index - stack_top - 1, not current_index - popped_index. Getting this wrong is the #1 bug in histogram solutions

When to Use

Matching or balancing pairs (brackets, tags, nested structures)

Valid parentheses or balanced in the problem name

Need O(1) access to the most recently added element

Undo/redo functionality or backtracking through states

Evaluating expressions (postfix, infix with precedence)

Processing elements in reverse order of insertion

Next greater element or next smaller element

How many days until a warmer temperature (next greater variant)

Largest rectangle or maximum area in histogram/matrix

The brute force is O(n²) scanning left/right for each element

Keywords: stack, parentheses, brackets, valid, balanced, next greater, next smaller, monotonic, histogram, temperature

Template

1# --- Basic Stack Usage ---
2stack = []
3stack.append(item)          # push
4top = stack[-1]             # peek
5item = stack.pop()          # pop
6if stack:                   # check not empty
7    # safe to peek/pop
8
9# --- Monotonic Stack: Next Greater Element ---
10def next_greater(nums):
11    n = len(nums)
12    result = [-1] * n
13    stack = []              # indices, maintaining decreasing values
14    for i in range(n):
15        # Pop elements smaller than current — current is their "next greater"
16        while stack and nums[i] > nums[stack[-1]]:
17            idx = stack.pop()
18            result[idx] = nums[i]
19        stack.append(i)
20    return result
21
22# --- Monotonic Stack: Next Smaller Element ---
23def next_smaller(nums):
24    n = len(nums)
25    result = [-1] * n
26    stack = []              # indices, maintaining increasing values
27    for i in range(n):
28        while stack and nums[i] < nums[stack[-1]]:
29            idx = stack.pop()
30            result[idx] = nums[i]
31        stack.append(i)
32    return result

{ }

Syntax Reference

1# --- Python: list as stack ---
2stack = []                    # Create empty stack
3stack.append(val)             # Push: O(1) amortized
4val = stack.pop()             # Pop: O(1), raises IndexError if empty
5top = stack[-1]               # Peek: O(1), raises IndexError if empty
6is_empty = len(stack) == 0    # Check empty: O(1)
7size = len(stack)             # Size: O(1)
8
9# --- Safe peek/pop ---
10if stack:                     # Check before peek/pop
11    top = stack[-1]
12    val = stack.pop()
13
14# --- collections.deque (alternative, O(1) from both ends) ---
15from collections import deque
16stack = deque()
17stack.append(val)             # Push right: O(1)
18val = stack.pop()             # Pop right: O(1)

📋

Common Recipes

1# --- Bracket Matching ---
2def is_valid(s):
3    stack = []
4    pairs = {')': '(', ']': '[', '}': '{'}
5    for ch in s:
6        if ch in '([{':
7            stack.append(ch)
8        elif not stack or stack.pop() != pairs[ch]:
9            return False
10    return len(stack) == 0
11
12# --- Next Greater Element (Monotonic Decreasing Stack) ---
13def next_greater(nums):
14    n = len(nums)
15    result = [-1] * n
16    stack = []  # stores indices
17    for i in range(n):
18        while stack and nums[i] > nums[stack[-1]]:
19            idx = stack.pop()
20            result[idx] = nums[i]
21        stack.append(i)
22    return result
23
24# --- Largest Rectangle in Histogram ---
25def largest_rect(heights):
26    stack = []  # stores indices of increasing heights
27    max_area = 0
28    for i, h in enumerate(heights):
29        start = i
30        while stack and stack[-1][1] > h:
31            idx, height = stack.pop()
32            max_area = max(max_area, height * (i - idx))
33            start = idx
34        stack.append((start, h))
35    for idx, height in stack:
36        max_area = max(max_area, height * (len(heights) - idx))
37    return max_area

O(n)

Complexity

Operation	Time	Space
Push / Pop / Peek	O(1)	O(1)
Bracket matching (n characters)	O(n)	O(n)
Next greater/smaller element (n elements)	O(n)	O(n)
Largest rectangle in histogram	O(n)	O(n)
Expression evaluation (n tokens)	O(n)	O(n)
Min Stack (push/pop/getMin)	O(1) each	O(n)

Watch Out

✗Not processing remaining stack elements: After iterating through the array, elements left in a monotonic stack have no "next greater/smaller" — you must handle them (usually set to -1 or 0)
✗Confusing increasing vs decreasing monotonic stack: A monotonically *decreasing* stack finds the next greater element. A monotonically *increasing* stack finds the next smaller element. This is counterintuitive
✗Storing values instead of indices: For most monotonic stack problems, store indices (not values) so you can compute distances or positions. You can always look up the value from the original array
✗Forgetting empty-stack checks: Always check if the stack is empty before peeking or popping — especially in bracket matching and monotonic stack problems
✗Off-by-one in histogram problems: When computing widths in the histogram problem, the width is `current_index - stack_top - 1`, not `current_index - popped_index`. Getting this wrong is the #1 bug in histogram solutions

PRACTICE PROBLEMS

Binary Search

Linked Lists