Monotonic Stack Interview Patterns: Next Greater Element, Largest Rectangle, and Daily Temperatures (2025)

The Monotonic Stack Pattern

A monotonic stack maintains elements in strictly increasing or strictly decreasing order. When a new element violates the order, elements are popped (processed) before the new element is pushed. This gives O(n) solutions to problems that ask “for each element, find the nearest element to its left/right that is greater/smaller.” The key insight: each element is pushed once and popped once, giving O(n) amortized despite the nested loop appearance. Two variants: Monotonic decreasing (bottom to top decreasing): use for “next greater element” problems. Monotonic increasing: use for “next smaller element” problems.

Next Greater Element (LC 496 / 503)

def next_greater_element(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []  # indices, values are decreasing

    for i in range(n):
        # Pop elements whose next greater element is nums[i]
        while stack and nums[stack[-1]]  list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    return result

Daily Temperatures (LC 739)

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices of unresolved days

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev = stack.pop()
            result[prev] = i - prev
        stack.append(i)
    return result

Largest Rectangle in Histogram (LC 84)

For each bar, find the width of the largest rectangle where it is the shortest bar (the bottleneck). Use a monotonic increasing stack: when a bar is shorter than the stack top, the stack top is the shortest bar in a rectangle that ends here. Pop and compute area.

def largest_rectangle_area(heights: list[int]) -> int:
    stack = []  # indices, heights are increasing
    max_area = 0
    heights = heights + [0]  # sentinel to flush remaining bars

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

Maximal Rectangle in Binary Matrix (LC 85)

Build a histogram for each row: heights[j] = number of consecutive 1s ending at (row, j). Run largest_rectangle_area on each row’s histogram. O(m*n) time.

def maximal_rectangle(matrix: list[list[str]]) -> int:
    if not matrix: return 0
    n = len(matrix[0])
    heights = [0] * n
    max_area = 0
    for row in matrix:
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0
        max_area = max(max_area, largest_rectangle_area(heights))
    return max_area

Other monotonic stack applications: Sum of Subarray Minimums (LC 907): for each element as the minimum, find the range it dominates. Maintain monotonic increasing stack, track left and right boundaries. Contribution = element * left_count * right_count. Stock Span Problem: monotonic decreasing stack of indices; for each day, pop days with lower or equal price — span = i – stack[-1] – 1 after popping. Asteroid Collision (LC 735): simulate collisions with a stack — push right-moving asteroids; on left-moving asteroid, pop right-movers if smaller.

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What makes a stack "monotonic" and why does it give O(n) solutions?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A monotonic stack maintains elements in sorted order (either increasing or decreasing from bottom to top). Before pushing a new element, elements that violate the ordering are popped. The key property: each element is pushed exactly once and popped at most once, so the total number of push + pop operations across all n elements is O(n). This gives O(n) total time despite the inner while loop. Contrast: a naive O(n^2) approach checks all pairs. The monotonic stack implicitly prunes: when element B is popped because element C is larger, we know C is the "next greater element" for B — no need to check any element between B and C.”}},{“@type”:”Question”,”name”:”For the Largest Rectangle in Histogram, why do we use a monotonic increasing stack?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”We want to find, for each bar, the extent to which it can expand left and right as the shortest bar in a rectangle. A bar can extend left/right until it hits a bar shorter than itself. A monotonic increasing stack (bottom to top: smallest to largest) naturally identifies this: when a bar h is about to be pushed but is smaller than the stack top, the stack top bar cannot extend right any further (the new shorter bar cuts it off). We pop the stack top and compute its rectangle: height = popped bar height, width = from the element now at stack top (the nearest shorter bar to the left) to the current index. The sentinel 0 at the end forces all remaining bars to be popped and processed.”}},{“@type”:”Question”,”name”:”How does the circular array variant of Next Greater Element work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For a circular array, each element's next greater element can be to its right OR, after wrapping around, to its left. The trick: iterate 2n times (0 to 2n-1) using index % n to access elements circularly. Only push to the stack for the first n indices (i < n) — this ensures each element appears in the stack exactly once as a "waiting" element. During the second pass (i >= n), we continue popping elements from the stack when a greater element is found, but do not push new elements (those indices are already in the stack from the first pass). This correctly resolves elements that wrap around. Result array initialized to -1 handles elements with no greater element.”}},{“@type”:”Question”,”name”:”How does Sum of Subarray Minimums (LC 907) use a monotonic stack?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For each element A[i] as the minimum, find: left[i] = number of subarrays ending at i where A[i] is the minimum (distance to the previous smaller element, strictly), right[i] = number of subarrays starting at i where A[i] is the minimum (distance to the next smaller or equal element). Contribution of A[i] to the total sum = A[i] * left[i] * right[i]. Use monotonic increasing stacks: one left-to-right pass computes left[i] (pop until a smaller element is found; left[i] = i – stack_top), one right-to-left pass computes right[i]. The asymmetric boundary (strictly smaller on left, smaller or equal on right) prevents double-counting equal elements. Total time O(n), space O(n).”}},{“@type”:”Question”,”name”:”What is the stock span problem and how does a monotonic stack solve it in O(n)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The stock span on day i is the number of consecutive days (including today) where the price was <= today's price. Naive: for each day, scan backward until you find a higher price — O(n^2). Monotonic decreasing stack of indices: maintain a stack where prices are decreasing from bottom to top. On day i: pop all stack entries with price <= today's price (they are within today's span). The span = i – index of the remaining stack top (the last day with a higher price). If stack is empty, span = i + 1 (all days up to today). Push today's index. Each element is pushed and popped once: O(n). The popped elements are consumed by today's span and never need to be considered again for future days (any future day that beats today also beats all the popped prices).”}}]}