Other

Monotonic Stack

TimeO(n) SpaceO(n)

Imagine standing in a crowd trying to see the stage. You can see the stage only if nobody taller is standing between you and it. A monotonic stack is like scanning the crowd from the back: each time a taller person appears, everyone shorter in front of them is “resolved” — they now know who blocks their view.

When to use it: Finding the next greater element, next smaller element, largest rectangle in a histogram, trapping rain water, or any problem where each element needs to find the nearest element that is larger (or smaller) than it.

Key insight: A monotonic decreasing stack ensures that when a larger element arrives, all smaller elements on the stack get “resolved” (they’ve found their next greater element). Each element is pushed and popped at most once, giving O(n) total.

Common trap: Getting the stack direction wrong. For “next greater element,” use a decreasing stack. For “next smaller element,” use an increasing stack. Think about what condition triggers a pop.

# Next Greater Element: for each element, find the first larger element to its right
function nextGreaterElement(arr):
    n = length(arr)
    result = array of size n, filled with -1       # default: no greater element
    stack = []                                      # stores indices

    for i = 0 to n - 1:
        # Pop elements smaller than current — current is their "next greater"
        while stack is not empty and arr[stack.top()] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]

        stack.push(i)

    return result

# Largest Rectangle in Histogram
function largestRectangle(heights):
    stack = []                      # stores indices of bars in increasing height
    maxArea = 0
    heights.append(0)               # sentinel to flush remaining bars

    for i = 0 to length(heights) - 1:
        while stack is not empty and heights[stack.top()] > heights[i]:
            h = heights[stack.pop()]
            w = i if stack is empty else i - stack.top() - 1
            maxArea = max(maxArea, h * w)

        stack.push(i)

    return maxArea

def next_greater_element(arr: list[int]) -> list[int]:
    """For each element, find the first larger element to its right. -1 if none."""
    n = len(arr)
    result = [-1] * n
    stack = []  # indices, maintaining decreasing order of values

    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result


def daily_temperatures(temperatures: list[int]) -> list[int]:
    """Days until a warmer temperature. 0 if none."""
    n = len(temperatures)
    result = [0] * n
    stack = []

    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)

    return result


def largest_rectangle_histogram(heights: list[int]) -> int:
    """Largest rectangular area in a histogram."""
    stack = []
    max_area = 0
    heights = heights + [0]  # sentinel

    for i in range(len(heights)):
        while stack and heights[stack[-1]] > heights[i]:
            h = heights[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)

    return max_area


def trap_rain_water(height: list[int]) -> int:
    """Total water trapped between bars using a monotonic stack."""
    stack = []
    water = 0

    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            w = i - stack[-1] - 1
            h = min(height[i], height[stack[-1]]) - height[bottom]
            water += w * h
        stack.append(i)

    return water

Problem: Given daily temperatures as an array, return an array where each element tells you how many days you have to wait until a warmer temperature. If no warmer day exists, return 0.

How would you approach this?

Answer: This is a monotonic (decreasing) stack problem. Push each day's index onto the stack. When a warmer day appears, pop all cooler days from the stack — the difference in indices is the wait time. Each element is pushed and popped at most once.

Problem: Given an array of bar heights representing a histogram, find the area of the largest rectangle that can be formed within the histogram.

How would you approach this?

Answer: This is monotonic stack (increasing). Maintain a stack of bar indices in increasing height order. When a shorter bar appears, pop taller bars and compute rectangles using them as the height. The width extends from the current position back to the new stack top.

Time: O(n) because each element is pushed onto the stack exactly once and popped at most once. Even though there is a while loop inside the for loop, the total number of pops across all iterations is bounded by n.

Space: O(n) for the stack, which in the worst case holds all n elements (e.g., a strictly decreasing input for a "next greater element" query).