Monotonic Stack

Intuition

A monotonic stack is an ordinary stack with one rule: from bottom to top its elements stay sorted (always increasing, or always decreasing). When a new element arrives, you first pop everything that would break the order, then push the newcomer.

That popping step is where all the information comes from. Suppose the stack is kept decreasing and a value x arrives:

• every element popped because it is smaller than x has just met its next greater element, which is x;
• the element left on top after the pops (if any) is the previous greater-or-equal element of x.

So a single left-to-right pass gives every element its nearest larger neighbor on one side and its nearest larger-or-equal neighbor on the other. Flip the comparison (keep the stack increasing) and you get next/previous smaller elements instead.

Why is it fast? Each index is pushed once and popped at most once, so the total work is O(n) even though a single step may pop many elements.

Store indices, not values. With an index you can read the value (nums[i]), compute distances (j - i), and know the boundaries of ranges.

The same pass also builds a Cartesian tree: a binary tree over the array whose in-order traversal is the original order and whose values satisfy the heap property (each parent is the maximum of its subtree). Each node's subtree is exactly the maximal range in which that element is the maximum, the same range the stack discovers. In interviews this shows up as "build the maximum binary tree" in O(n).

When to use it in interviews / OAs

• Nearest larger/smaller element on either side: next greater element, daily temperatures ("how many days until a warmer one?"), stock span, previous smaller element.
• "For each element, over which range is it the minimum/maximum?" This is the contribution technique: largest rectangle in a histogram, maximal rectangle of 1s in a matrix, sum of subarray minimums, sum of subarray ranges, counting subarrays where an element is the maximum.
• Greedy lexicographic choices: remove k digits to make the smallest number, smallest subsequence with distinct letters. The stack holds the answer built so far and pops a larger previous character when a smaller one can replace it.
• Visibility problems: how many people each person can see in a queue, buildings with an ocean view, trapping rain water (stack variant).
• Tree construction from an array: maximum binary tree, checking whether a sequence can be a BST preorder.

If the question needs the maximum of every window of fixed size, use the deque-based monotonic queue instead (separate article).

Template

Both reading directions in one place: the answer for the elements being popped (next greater) and the answer for the element being pushed (previous smaller).

def next_greater(nums: list[int]) -> list[int]:
    ans = [-1] * len(nums)
    stack: list[int] = []  # Indices still waiting for an answer; their values decrease upward.
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x  # x is the next greater element of everything it pops.
        stack.append(i)
    return ans  # Indices left on the stack keep -1: nothing greater follows them.


def previous_smaller(nums: list[int]) -> list[int]:
    ans = [-1] * len(nums)
    stack: list[int] = []  # Values increase upward.
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] >= x:
            stack.pop()
        ans[i] = nums[stack[-1]] if stack else -1  # Whatever survives on top is the previous smaller.
        stack.append(i)
    return ans


assert next_greater([2, 1, 2, 4, 3]) == [4, 2, 4, -1, -1]
assert previous_smaller([3, 1, 4, 1, 5]) == [-1, -1, 1, -1, 1]

Largest rectangle in a histogram. When a bar is popped, the current index is the first lower bar on its right and the new top of the stack is the first lower bar on its left, so the popped bar's height spans everything strictly between them.

def largest_rectangle(heights: list[int]) -> int:
    stack: list[int] = []  # Indices of bars with increasing heights.
    best = 0
    for i, h in enumerate(heights + [0]):  # A trailing 0 flushes every bar at the end.
        while stack and heights[stack[-1]] >= h:
            top = stack.pop()  # i is the first bar to the right that is lower than top.
            left = stack[-1] if stack else -1  # The new top is the previous lower bar.
            best = max(best, heights[top] * (i - left - 1))
        stack.append(i)
    return best


assert largest_rectangle([2, 1, 5, 6, 2, 3]) == 10
assert largest_rectangle([2, 4]) == 4 and largest_rectangle([]) == 0

The contribution technique: instead of enumerating O(n^2) subarrays, ask for each element how many subarrays have it as their minimum. With L choices for the left end and R for the right end, it contributes value * L * R. Duplicates need care: make one side strict and the other non-strict so each subarray is credited to exactly one of its equal minima.

def sum_subarray_mins(arr: list[int]) -> int:
    n = len(arr)
    left, right, stack = [0] * n, [0] * n, []
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:  # Strict: an equal value on the left stops us.
            stack.pop()
        left[i] = i - (stack[-1] if stack else -1)  # Choices for the left end.
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:  # Non-strict here, so ties are counted exactly once.
            stack.pop()
        right[i] = (stack[-1] if stack else n) - i  # Choices for the right end.
        stack.append(i)
    # arr[i] is the minimum of left[i] * right[i] subarrays.
    return sum(a * l * r for a, l, r in zip(arr, left, right))


assert sum_subarray_mins([3, 1, 2, 4]) == 17
assert sum_subarray_mins([2, 2]) == 6

Building a max-Cartesian tree (the "maximum binary tree") in O(n). The stack holds the right spine of the tree built so far. Elements popped by nums[i] become its left subtree, and i hangs as the right child of whatever remains on top.

def build_max_tree(nums: list[int]) -> tuple[int, list[int], list[int]]:
    # Returns (root, left, right): child indices, -1 for none.
    n = len(nums)
    left, right = [-1] * n, [-1] * n
    stack: list[int] = []  # The right spine of the tree so far; values decrease upward.
    for i in range(n):
        last = -1
        while stack and nums[stack[-1]] < nums[i]:
            last = stack.pop()  # Popped nodes leave the spine and become i's left subtree.
        left[i] = last
        if stack:
            right[stack[-1]] = i  # i becomes the right child of the new spine end.
        stack.append(i)
    return (stack[0] if stack else -1), left, right


root, L, R = build_max_tree([3, 2, 1, 6, 0, 5])
assert root == 3 and L[3] == 0 and R[3] == 5 and R[0] == 1 and L[5] == 4

Complexity

• Time: O(n) for each pass, since every index is pushed and popped at most once.
• Space: O(n) for the stack and the answer arrays.
• Circular arrays: run the loop over 2n positions using i % n, pushing only during the first lap. Still O(n).

Common pitfalls

• Picking the wrong monotonic direction. Next greater needs a stack whose values decrease toward the top (smaller ones get popped); next smaller needs an increasing stack.
• Strict vs non-strict comparisons. < vs <= decides what happens with equal values. For "next strictly greater" pop on <; for contribution counting, use strict on one side and non-strict on the other, or you will double count (or miss) subarrays with repeated minima.
• Forgetting the leftovers. Elements still on the stack at the end have no next greater element. Initialize answers to a default (-1 or n), or push a sentinel (like the trailing 0 in the histogram) to flush them.
• Storing values instead of indices. You lose positions and cannot compute widths or distances.
• Overflow and modulo. Sums like "sum of subarray minimums" grow fast; in Java/C++ use 64-bit integers or take the modulo the problem asks for.

Interview variations

• Next greater element I/II (II is circular), daily temperatures, online stock span (store (price, span) pairs and merge spans while popping).
• Largest rectangle in a histogram, maximal rectangle (treat each row as the base of a histogram of consecutive 1s).
• Sum of subarray minimums, sum of subarray ranges (sum of maxima minus sum of minima), number of subarrays with a bounded maximum.
• Trapping rain water: when a bar pops, it is the floor; water above it is bounded by the new top on the left and the current bar on the right.
• Remove k digits, remove duplicate letters, create the maximum number from two arrays.
• Maximum binary tree (Cartesian tree), verify a preorder sequence of a BST.
• 132 pattern: scan from the right with a decreasing stack, tracking the largest value popped as the candidate middle element.
• Number of visible people in a queue, car fleet, buildings with an ocean view.