Monotonic stack

The pattern that turns an obvious O(n²) into O(n). Recognisable by a specific question shape, and once you see the shape the code is nearly mechanical.

The trigger

Reach for it when the question is “for each element, find the nearest element to its left/right that is greater/smaller” — or anything that reduces to that.

Common phrasings: next greater element, daily temperatures, largest rectangle in a histogram, trapping rain water, stock span, remove digits to make the smallest number.

The mechanic

Keep a stack whose values are always increasing (or always decreasing). When a new element violates that order, pop — and each pop is an answer.

def next_greater(nums: list[int]) -> list[int]:
    """For each element, the next strictly greater element to its right (-1 if none)."""
    result = [-1] * len(nums)
    stack: list[int] = []                    # indices, values decreasing

    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            result[stack.pop()] = n          # n is the answer for that popped index
        stack.append(i)

    return result

Store indices, not values. You almost always need the position — for a distance, a width, or to write into a result array.

Why it’s O(n) despite the inner while: each index is pushed once and popped at most once, so total work across the whole loop is bounded by 2n. This amortised argument is the thing to state in an interview.

Increasing or decreasing

The rule confuses everyone once. Derive it rather than memorising:

The stack holds elements still waiting for an answer. If you’re looking for the next greater element, anything smaller than the current value has just found its answer — so pop it.

Largest rectangle in a histogram

The hardest common application, and worth knowing because several problems reduce to it.

def largest_rectangle(heights: list[int]) -> int:
    stack: list[int] = []                    # indices, heights increasing
    best = 0
    heights = heights + [0]                  # sentinel forces a full drain

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1             # bounded by the new left and right neighbours
            best = max(best, height * width)
        stack.append(i)

    return best

Two details that make it work:

• The sentinel 0 guarantees every bar is popped, so you don’t need a separate drain loop.
• width = i - left - 1 — when you pop a bar, i is the first smaller bar to its right and stack[-1] is the first smaller to its left. The rectangle spans strictly between them.

“Maximal rectangle in a binary matrix” is this function applied row by row over accumulated heights.

Trapping rain water

Solvable with a monotonic stack, but the two-pointer solution is simpler and O(1) space — worth knowing both and preferring the latter.

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = total = 0

    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            total += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            total += right_max - height[right]
            right -= 1

    return total

The insight: water above a position is bounded by min(max_left, max_right). Moving the pointer at the smaller side is safe, because that side’s maximum is the binding constraint.

Monotonic deque — sliding window maximum

The same idea with a deque, for windowed problems:

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()                 # indices, values decreasing
    out = []

    for i, n in enumerate(nums):
        while dq and nums[dq[-1]] < n:       # smaller values can never be the max again
            dq.pop()
        dq.append(i)

        if dq[0] <= i - k:                   # front has left the window
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])

    return out

The front of the deque is always the window maximum. Elements smaller than a newer element are useless — the newer one is bigger and stays in the window longer.

Interview angle

• “When do you reach for a monotonic stack?” — when the question asks, for each element, for the nearest greater or smaller element in some direction. Recognising that shape is most of the work; the code is nearly mechanical afterwards.
• “Why is it O(n) when there’s a nested while loop?” — amortised analysis. Each index is pushed once and popped at most once, so total pops across the whole run are bounded by n, giving O(n) overall.
• “Increasing or decreasing stack?” — derive it: the stack holds elements still waiting for an answer. For next-greater, pop anything smaller than the current element, which leaves a decreasing stack.
• “Why store indices rather than values?” — you almost always need the position to compute a width or distance, and you can always recover the value.
• “Largest rectangle in a histogram — the key step?” — when you pop a bar, the current index is its first smaller bar to the right and the new stack top is its first smaller to the left, so the width is i - stack[-1] - 1. Append a zero sentinel so everything drains.
• “Trapping rain water — stack or two pointers?” — two pointers: O(n) time and O(1) space, and simpler to reason about. Water at a position is bounded by min(max_left, max_right), so advancing the smaller side is always safe.