Stacks & Monotonic Stacks

Stacks are deceptively simple LIFO structures whose real interview power comes from monotonic stack patterns — maintaining elements in sorted order to answer next-greater/next-smaller queries in O(n) instead of O(n²). Monotonic stacks underlie solutions to histogram rectangles, rain water trapping, daily temperatures, stock span, and many more. These are among the most commonly asked 'clever O(n)' problems at FAANG.

Arrays and indexingBig-O analysisPython list as stackMonotonic StackNext Greater ElementLargest RectangleTrapping Rain WaterMin StackValid Parentheses

Core Concepts

1Stack fundamentals: a stack is a LIFO (Last In First Out) collection supporting push (append to top), pop (remove from top), and peek (read top without removing). In Python, use a list: stack.append(x) to push, stack.pop() to pop, stack[-1] to peek. Always check 'if stack' before pop/peek to avoid IndexError. Time O(1) per operation. Stacks model recursive call frames, balanced parentheses, expression evaluation, and undo operations.
2Monotonic decreasing stack (next greater element): maintain a stack of elements in strictly decreasing order from bottom to top. For each new element x: while the stack is not empty AND the top element is less than x, pop the top — x is the 'next greater element' for the popped value. Push x. After processing all elements, anything remaining on the stack has no next greater element. The total number of pushes and pops is O(n) — each element is pushed once and popped at most once.
3Monotonic increasing stack (previous smaller element): maintain a stack in strictly increasing order. For each new element x: while the stack top is >= x, pop. After popping, if the stack is empty, there is no previous smaller element to the left. Otherwise, the stack top is the nearest smaller element to the left. Push x. This pattern solves 'for each element, find the nearest smaller element to its left' in O(n).
4Largest rectangle in histogram (LC 84): for each bar, the largest rectangle using that bar as the shortest bar extends left to the nearest shorter bar and right to the nearest shorter bar. Use a monotonic increasing stack of indices. When a bar shorter than the stack top is encountered, pop bars that are taller — for each popped bar of height h, the width is (current_index - stack_top_after_pop - 1). An appended sentinel bar of height 0 at the end ensures all bars are popped. Time O(n), Space O(n).
5Trapping Rain Water with a stack (LC 42): maintain a stack of indices with non-increasing heights. When a taller bar is encountered at index i, there is a potential water pit between the current bar and the bar under the stack top. Pop the bottom of the pit, compute the trapped height as min(height[stack top], height[i]) - height[popped], compute width as i - stack_top - 1, accumulate water += height * width. Continue until stack is empty or current bar is not taller. Time O(n), Space O(n).
6Min Stack (LC 155): support push, pop, top, and getMin in O(1). Use two stacks: the main stack and an auxiliary min-stack. On push(x): push x to main stack; push min(x, min_stack[-1]) to min stack (or just x if min stack is empty). On pop: pop from both stacks simultaneously. getMin: return min_stack[-1]. The min stack always records the minimum of all elements currently in the main stack, synchronized in size.
7Valid parentheses and bracket matching (LC 20): push opening brackets onto the stack. When a closing bracket is encountered, check if the stack is non-empty and the top is the matching opener — if so, pop. If not, return False. After processing all characters, return True only if the stack is empty (all openers were matched). Extension: for 'minimum add to make parentheses valid' problems, count unmatched openers left on the stack plus unmatched closers encountered.
8Decode String (LC 394): nested bracket decoding uses a stack of (current_string, multiplier) pairs. When '[' is encountered: push (current_string, multiplier) and reset both. When ']' is encountered: pop (prev_string, k) and set current_string = prev_string + k * current_string. Append regular characters to current_string. Track multiplier as digits before '['. The stack cleanly handles arbitrary nesting depth.

Key Patterns & Templates

Monotonic decreasing stack (next greater): while stack and stack[-1] < x: result[stack.pop()] = x; stack.append(x)

Monotonic increasing stack (previous smaller): while stack and stack[-1] >= x: stack.pop(); prev_small = stack[-1] if stack else -1; stack.append(x)

Largest rectangle: stack of indices; when heights[i]<heights[stack[-1]]: pop, width=i-stack[-1]-1 (or i if empty), area=h*w

Min stack: parallel min_stack; push min(x, min_stack[-1]); pop both together; getMin = min_stack[-1]

Valid parentheses: push openers; on closer: if stack and top matches opener: pop; else False; end: return not stack

Evaluate RPN: push numbers; on operator: b=pop, a=pop, push a op b; handle integer division toward zero with int(a/b)

Decode string: stack of (string, multiplier); on '[': push and reset; on ']': pop and expand; append chars

Circular next greater (LC 503): iterate 2n indices with i%n; process as monotonic stack; only push when i<n

Worked Examples

Given an array of non-negative integers representing the histogram's bar heights, find the area of the largest rectangle in the histogram.

1Step 1 — Brute force: for each pair (i, j), the rectangle height is min(heights[i..j]), width is j-i+1. O(n³) naive or O(n²) with running min. Not acceptable.

2Step 2 — Key insight: for each bar i with height h[i], the largest rectangle using h[i] as the minimum extends left to the first bar shorter than h[i] (exclusive) and right to the first bar shorter than h[i] (exclusive). We need these boundaries in O(1) per bar — use a monotonic stack.

3Step 3 — Algorithm: maintain a monotonic increasing stack of indices. When h[i] < h[stack top], the bar at stack top has found its right boundary (index i). Its left boundary is the new stack top after popping. Width = i - new_stack_top - 1. Area = h[popped] * width.

4Step 4 — Sentinel: append a height-0 bar at the end. This triggers popping of all remaining bars at the end, so no special post-loop code is needed. Without the sentinel, bars that never find a shorter bar to their right stay on the stack unprocessed.

5Step 5 — Width formula when stack is empty: when the stack is empty after popping (the popped bar was the global minimum), the left boundary extends to index -1. Width = i - (-1) - 1 = i. This is correct: the rectangle spans from index 0 to i-1.

6Step 6 — Complexity: each of the n bars (plus sentinel) is pushed once and popped at most once. Total O(n) operations. Space O(n) for the stack.

✓ Time O(n), Space O(n). The sentinel (appending height 0) is the key implementation trick that avoids a post-loop cleanup pass. Articulating the 'left boundary = new stack top, right boundary = current i' width formula precisely is what distinguishes candidates who truly understand the algorithm from those who memorized it.

Common Mistakes

⚠

Confusing monotonic increasing vs. decreasing: monotonic increasing stacks find the 'previous smaller' and 'next smaller' elements (pop when current < top). Monotonic decreasing stacks find 'previous greater' and 'next greater' (pop when current > top). Drawing 3-4 elements on paper and tracing which elements pop which is the fastest way to verify direction before coding.

⚠

In largest rectangle histogram, computing width incorrectly when the stack is empty after popping: when you pop index j and the stack is then empty, the left boundary is -1 (the rectangle spans from the leftmost bar). Width = i - (-1) - 1 = i, NOT i - 0 - 1 = i - 1. Using stack[-1] without guarding for empty stack causes an IndexError or wrong result. Always write: left = stack[-1] if stack else -1.

⚠

In evaluate RPN, using Python's // operator for division: Python's floor division (//) rounds toward negative infinity, but the problem requires truncation toward zero. For example, -7 // 2 = -4 in Python but should be -3. Use int(a / b) or math.trunc(a / b) instead. This is a language-specific gotcha that will silently fail on negative test cases.

⚠

Not handling multi-digit numbers in decode string: when parsing a multiplier like '12', reading one character at a time gives '1' then '2' as separate digits. Use current_num = current_num * 10 + int(ch) to accumulate digits. The same pattern applies to any problem requiring parsing of multi-digit integers from a string character by character.

Back to SWE Hub