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]
    """
    answer = [0] * len(temperatures)
    stack: list[int] = []          # indices of days still waiting; temps decreasing

    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.
        while stack and temperatures[stack[-1]] < temperature:
            earlier = stack.pop()
            answer[earlier] = index - earlier

        stack.append(index)

    # 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.

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
    stack: list[int] = []          # indices; nums[stack] is non-increasing

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

        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.

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] = {}
    stack: list[int] = []          # values this time, since nums2 has no duplicates

    for value in nums2:
        while stack and stack[-1] < value:
            greater[stack.pop()] = value
        stack.append(value)

    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
    stack: list[int] = []          # indices; heights non-increasing

    for right, bar in enumerate(height):
        # A taller bar closes off one or more basins to its left.
        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]
            width = right - left - 1
            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

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    total = 0

    while left < right:
        if left_max <= right_max:
            left += 1
            left_max = max(left_max, height[left])
            total += left_max - height[left]
        else:
            right -= 1
            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.

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
    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.
    for index, bar in enumerate([*heights, 0]):
        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.
            left = stack[-1] + 1 if stack else 0
            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.

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.
    """
    if not matrix or not matrix[0]:
        return 0

    heights = [0] * len(matrix[0])
    best = 0

    for row in matrix:
        for c, cell in enumerate(row):
            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.