Monotonic Stack

1. Daily Temperatures Medium

Problem

Given daily temperatures, return an array where answer[i] is the number of days you must wait after day i for a warmer temperature. If no warmer day comes, put 0.

Approach

• This is “next greater element” asking for a distance rather than a value. That is why the stack holds indices.
• Keep the stack decreasing. A day still on the stack has not yet seen anything warmer.
• When a warmer day arrives, it resolves every colder day waiting below it, and the wait is the difference of the two indices.
• Days left on the stack never warm up, and the array is pre-filled with 0, so no cleanup is needed.

Solution

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """Days to wait for a warmer temperature, per day.

    Args:
        temperatures: Daily temperature readings.

    Returns:
        answer[i] is the number of days after i until a warmer day, or 0.

    Example:
        >>> daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])
        [1, 1, 4, 2, 1, 1, 0, 0]
    """
    # 0 means "no warmer day ahead". Days that never warm up keep it.
    answer = [0] * len(temperatures)
    stack: list[int] = []          # indices of days still waiting. Temps decrease

    # index is today. Invariant: the stack holds every earlier day
    # with no warmer day yet, coldest on top.
    for index, temperature in enumerate(temperatures):
        # This day is warmer than everything waiting on top of the stack,
        # so it is the answer for all of them. stack[-1] is the top.
        while stack and temperatures[stack[-1]] < temperature:
            earlier = stack.pop()
            answer[earlier] = index - earlier   # days waited: the gap in index

        stack.append(index)        # today now waits for its own warmer day

    # Whatever is still stacked never warmed up, and 0 is already there.
    return answer

Walkthrough

[73, 74, 75, 71, 69, 72, 76, 73]:

Indices 6 and 7 stay stacked and keep their 0.

Reading the figure. Each bar is one day. A red arrow runs from a day to the warmer day that popped it off the stack. The cell under each bar is the wait, which is the gap between the two day numbers. Green days found an answer. Blue days 6 and 7 never get popped, so they keep 0.

Worst case for space is a strictly decreasing input, where nothing is ever popped and the stack holds all n indices. Worth naming when asked.

Edge cases to raise

• Strictly increasing input: every day pops the previous one, so every answer is 1 except the last.
• Strictly decreasing input: all zeros, and peak stack usage.
• All equal: < is strict, so nothing pops and all answers are 0. Correct, since equal is not warmer. Confirm that reading.
• Single day, or empty input.

2. Next Greater Element II Medium

Problem

Given a circular array, return the next greater element for each position. Searching wraps around past the end and back to the start. Use -1 where none exists.

The circular trick

Approach

• Same decreasing stack as problem 1.
• Write the value rather than the distance, because this problem asks for the element.
• The if i < n guard on the push is the entire difference from the non-circular version.

Solution

def next_greater_elements(nums: list[int]) -> list[int]:
    """Next greater element for each position in a circular array.

    Args:
        nums: The circular array. Searching wraps past the end.

    Returns:
        answer[i] is the first value greater than nums[i], scanning forward
        and wrapping around, or -1 if there is none.

    Example:
        >>> next_greater_elements([1, 2, 1])
        [2, -1, 2]
    """
    n = len(nums)
    answer = [-1] * n              # -1: "no greater value", the default
    stack: list[int] = []          # indices. nums[stack] is non-increasing

    # Two laps. The first seeds the stack, the second resolves the wrap-around.
    # 2 * n: i runs over both laps, 0..2n-1.
    for i in range(2 * n):
        value = nums[i % n]        # % n: wrap i back into 0..n-1

        # stack[-1] is the top: the most recent index still waiting.
        while stack and nums[stack[-1]] < value:
            answer[stack.pop()] = value

        if i < n:                  # never push on the second lap
            stack.append(i)

    return answer

Walkthrough

nums = [1, 2, 1], so the loop runs 6 times:

Index 1 holds the array maximum, so it correctly keeps -1.

Reading the figure. The six cells are the loop running 2n times over [1, 2, 1]. Blue cells are lap 1, where indices are pushed. Dashed cells are lap 2, where nothing is pushed. Each green arc is a pop that writes an answer. Index 2 only finds its answer because lap 2 wraps back to the 2 at the front.

2n iterations is still O(n). Do not let the doubling talk you into calling it quadratic.

The non-circular sibling

def next_greater_element_i(nums1: list[int], nums2: list[int]) -> list[int]:
    """Next Greater Element I: nums1 is a subset of nums2. Solve on nums2, then look up."""
    greater: dict[int, int] = {}   # value -> its next greater value in nums2
    stack: list[int] = []          # values this time, since nums2 has no duplicates

    # Invariant: the stack holds earlier values with no greater value yet.
    for value in nums2:
        # stack[-1] is the top. value is the answer for every smaller one there.
        while stack and stack[-1] < value:
            greater[stack.pop()] = value
        stack.append(value)

    # -1: values never popped have no greater value to the right.
    return [greater.get(value, -1) for value in nums1]

Here the values are guaranteed distinct, so a value-keyed map is safe and the stack can hold values directly. When duplicates are possible, go back to indices.

Edge cases to raise

• All equal, such as [5, 5, 5]: all -1, because < is strict.
• The maximum element always gets -1, and there may be several copies of it.
• Single element: [-1].
• Strictly decreasing input: the wrap-around resolves everything except the first element.

3. Trapping Rain Water Hard

Problem

Given an elevation map where height[i] is the height of a bar of width 1, compute how much rain water is trapped after it rains.

The governing fact

Solution: monotonic stack, filling layer by layer

def trap(height: list[int]) -> int:
    """Total rain water trapped above an elevation map.

    Fills the terrain in horizontal layers. Each pop identifies a basin
    floor, with the popped bar's left neighbour on the stack as one wall
    and the arriving bar as the other.

    Args:
        height: Non-negative bar heights.

    Returns:
        Total trapped water.

    Example:
        >>> trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
        6
    """
    total = 0                      # 0: no water counted yet
    stack: list[int] = []          # indices. Heights non-increasing

    # right is the arriving bar. Invariant: the stack holds bars that may
    # still be a left wall, tallest at the bottom.
    for right, bar in enumerate(height):
        # A taller bar closes off one or more basins to its left.
        # stack[-1] is the top: the lowest waiting bar.
        while stack and height[stack[-1]] < bar:
            floor = stack.pop()

            if not stack:
                break              # no left wall, so the water spills out

            left = stack[-1]       # the new top is the left wall
            # - 1: count only the cells strictly between the two walls.
            width = right - left - 1
            # Water rises to the lower wall, above the floor already filled.
            depth = min(height[left], bar) - height[floor]
            total += width * depth

        stack.append(right)

    return total

Solution: two pointers, O(1) space

def trap_two_pointers(height: list[int]) -> int:
    """Same answer in O(1) space, converging from both ends.

    The insight: if the tallest bar seen from the left is no taller than the
    tallest seen from the right, then the left maximum is the binding wall
    for the left position, whatever lies in between. So it is safe to settle
    that side immediately.
    """
    if not height:
        return 0                   # 0: no bars, so no water

    # 0 is the first index. len - 1 is the last index.
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    total = 0                      # 0: no water counted yet

    # Invariant: every bar outside left..right is settled and counted.
    # left_max and right_max are the tallest bars seen from each side.
    while left < right:
        if left_max <= right_max:
            left += 1              # +1: step the left pointer inward
            left_max = max(left_max, height[left])
            # Water here is the wall height minus the bar. 0 if it is the wall.
            total += left_max - height[left]
        else:
            right -= 1             # -1: step the right pointer inward
            right_max = max(right_max, height[right])
            total += right_max - height[right]

    return total

The three solutions, ranked

Walkthrough of the stack version

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. At index 3 the bar of height 2 arrives. It pops the 0 at index 2, finds index 1 underneath as the left wall, and adds width 1 × depth (min(1, 2) - 0) = 1. Later the bar of height 3 at index 7 pops a run of small bars and adds the large middle basin. The layers accumulate to 6.

Reading the figure. The numbers under the bars are the heights. Each blue block is one layer of water. Its number is width times depth. A block appears when a taller bar arrives and pops a lower one. The wide block of 3 sits on top of a smaller one. A later pop can fill above an earlier layer.

Edge cases to raise

• Monotonic terrain, increasing or decreasing: traps nothing.
• Fewer than 3 bars: traps nothing, since water needs two walls and a floor.
• A flat plateau: nothing trapped, and the strict < in the stack version keeps equal bars stacked so no zero-depth basins are counted.
• Empty input: guarded in the two-pointer version, and naturally handled in the stack version.
• Leading and trailing zeros: contribute nothing, since there is no wall outside them.

4. Largest Rectangle in Histogram Hard

Problem

Given bar heights of width 1, find the area of the largest rectangle that fits inside the histogram.

The reframing

Once you say “each bar is the height, and I need its left and right smaller boundaries”, the problem is finished. Getting there is the interview.

Approach

• Keep an increasing stack of indices, because now we are hunting for smaller boundaries, not bigger ones.
• When a bar arrives that is not taller than the stack top, the top has found its right boundary. Pop it and compute its rectangle.
• After popping, whatever is left underneath is that bar’s left boundary. One pop yields both walls, which is why a single pass suffices.
• Append a sentinel of height 0. It is shorter than every real bar, so it drains the stack inside the loop and removes the cleanup block entirely.

Solution

def largest_rectangle_area(heights: list[int]) -> int:
    """Area of the largest rectangle that fits under a histogram.

    Each bar is considered as the limiting height of a rectangle. Its width
    runs between the nearest shorter bar on each side, both of which fall out
    of a single increasing stack.

    Args:
        heights: Non-negative bar heights, each of width 1.

    Returns:
        The maximum rectangle area.

    Example:
        >>> largest_rectangle_area([2, 1, 5, 6, 2, 3])
        10
    """
    best = 0                       # 0: the empty rectangle, area 0
    stack: list[int] = []          # indices. Heights strictly increasing

    # The trailing 0 is shorter than any bar, so it flushes the stack and
    # every bar gets resolved inside the loop.
    # Invariant: each stacked bar is taller than the one below it.
    for index, bar in enumerate([*heights, 0]):
        # stack[-1] is the top. index is the nearest shorter bar to its right.
        while stack and heights[stack[-1]] >= bar:
            height = heights[stack.pop()]

            # Left boundary: whatever is now on top is the nearest shorter
            # bar to the left. If the stack is empty, the rectangle reaches
            # all the way to index 0.
            # + 1: the rectangle starts just past that shorter bar.
            left = stack[-1] + 1 if stack else 0
            # Width runs from left up to index - 1, so it is index - left.
            best = max(best, height * (index - left))

        stack.append(index)

    return best

Walkthrough

heights = [2, 1, 5, 6, 2, 3]:

The winner is the 5 × 2 rectangle spanning the bars of height 5 and 6.

Reading the figure. The dashed green box is the winning rectangle. Its height comes from the bar of 5 (blue). The red bar is the nearest shorter bar on the left, and it sits under the 5 on the stack. The amber bar is the nearest shorter bar on the right, and its arrival pops the 5. The width is the gap between the two walls.

The follow-up: Maximal Rectangle in a binary matrix

def maximal_rectangle(matrix: list[list[str]]) -> int:
    """Largest all-ones rectangle in a binary matrix.

    Treat each row as the base of a histogram whose bar heights are the
    runs of ones stacked above that row. Then it is this problem, once per row.
    """
    # matrix[0] is the first row. An empty first row means no columns.
    if not matrix or not matrix[0]:
        return 0                   # 0: no cells, so no rectangle

    # One bar per column. matrix[0] gives the column count. 0: no ones yet.
    heights = [0] * len(matrix[0])
    best = 0                       # 0: no rectangle found yet

    # Invariant: heights[c] = run of "1" cells ending at this row in column c.
    for row in matrix:
        for c, cell in enumerate(row):
            # + 1 extends the run by this cell. 0 resets it on a "0" cell.
            heights[c] = heights[c] + 1 if cell == "1" else 0

        best = max(best, largest_rectangle_area(heights))

    return best

A Hard problem that becomes eight lines once you own the histogram routine. Worth knowing that this is why the histogram problem is asked at all.

Edge cases to raise

• All equal heights: one rectangle spanning everything, area h × n.
• Strictly increasing: each bar extends right to the end, and the sentinel resolves them all.
• Strictly decreasing: each bar extends left to index 0.
• Zero heights inside the input: they pop everything above them, which is correct, since a zero blocks any rectangle.
• Empty input: the loop sees only the sentinel and returns 0.
• >= rather than > means equal bars are popped early with a short width. That is safe, because the leftmost of the equal run is popped last and gets the full width.