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.

See also: Meta Interview Prep

See also: Atlassian Interview Prep

See also: Snap Interview Prep