Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Each bar in the histogram has width 1, and the goal is to find the largest possible rectangle that can be formed by taking one or more adjacent bars.

The important detail is that once a rectangle spans multiple bars, its height is limited by the shortest bar inside that span.

So the real question is not just “which span is widest?” It is:

“For each bar, how far can this height extend left and right before a shorter bar blocks it?”

If that span is known, then that bar can act as the limiting height of exactly one maximal rectangle:

  • height = heights[i]
  • width = right_boundary - left_boundary - 1
  • area = height * width

The challenge is finding those boundaries efficiently for every bar.

Why the brute-force idea is too slow

The most direct approach is to treat every bar as the rectangle height and expand outward until a shorter bar appears on either side.

That is correct, but in the worst case it rechecks the same bars over and over. For an increasing histogram like [1, 2, 3, 4, 5], each position may scan a large portion of the array, which pushes the runtime to O(n^2).

That is usually too slow for the full problem constraints.

The key insight: each bar needs its first smaller neighbor on both sides

Suppose bar i has height h.

If the first smaller bar on the left is at index left_smaller, and the first smaller bar on the right is at index right_smaller, then the largest rectangle that uses height h is forced to live strictly between those two indices.

That means:

  • left boundary of the rectangle is left_smaller + 1
  • right boundary of the rectangle is right_smaller - 1
  • width is right_smaller - left_smaller - 1

So the whole problem becomes:

“How do we find the first smaller bar to the left and right for every index in linear time?”

How to derive the optimal monotonic-stack solution

The cleanest way is to scan from left to right while maintaining a stack of indices whose heights are in increasing order.

Why increasing?

Because if the current bar is shorter than or equal to the bar on top of the stack, then the older bar on top has reached the point where keeping it no longer helps. Its maximal rectangle can be computed now, and if the heights are equal, the newer bar is the better one to keep because it can extend at least as far to the right.

When a bar is popped:

  • the current index is the first smaller bar on the right
  • the new top of the stack is the first smaller bar on the left
  • the popped bar is the limiting height

That gives its full rectangle width in one shot.

This is the part that makes the algorithm feel almost magical the first time: bars stay on the stack only while they can still potentially extend farther to the right. The moment a shorter or equal-height bar appears, that older possibility is finished, and the area for the popped bar can be finalized.

To flush out any remaining bars at the end, the standard trick is to append a sentinel bar of height 0. That artificial bar is smaller than everything, so it forces all unresolved bars to be popped and processed.

Each index is pushed once and popped once, so the total runtime is O(n).

Python solution

from __future__ import annotations

from dataclasses import dataclass
from typing import List, Sequence


@dataclass(frozen=True)
class RectangleCandidate:
    """Represents one maximal rectangle discovered during the scan."""

    left_index: int
    right_index: int
    height: int

    @property
    def width(self) -> int:
        return self.right_index - self.left_index + 1

    @property
    def area(self) -> int:
        return self.height * self.width


class HistogramAnalyzer:
    """Compute the largest rectangle area in a histogram."""

    def largest_rectangle_area(self, heights: Sequence[int]) -> int:
        """
        Return the maximum rectangle area that can be formed from adjacent bars.

        Time: O(n)
        Extra space: O(n)
        """
        self._validate_heights(heights)

        best_area = 0
        increasing_indices: List[int] = []
        extended_heights = list(heights) + [0]

        for current_index, current_height in enumerate(extended_heights):
            while (
                increasing_indices
                and extended_heights[increasing_indices[-1]] >= current_height
            ):
                candidate = self._build_candidate(
                    heights=extended_heights,
                    stack=increasing_indices,
                    right_smaller_index=current_index,
                )
                best_area = max(best_area, candidate.area)

            increasing_indices.append(current_index)

        return best_area

    def _build_candidate(
        self,
        heights: Sequence[int],
        stack: List[int],
        right_smaller_index: int,
    ) -> RectangleCandidate:
        """
        Pop one bar whose maximal right boundary is now known.

        After the pop:
        - ``right_smaller_index`` is the first smaller bar on the right
        - the new stack top is the first smaller bar on the left
        """
        height_index = stack.pop()
        height = heights[height_index]

        left_smaller_index = stack[-1] if stack else -1
        left_index = left_smaller_index + 1
        right_index = right_smaller_index - 1

        return RectangleCandidate(
            left_index=left_index,
            right_index=right_index,
            height=height,
        )

    def _validate_heights(self, heights: Sequence[int]) -> None:
        if not heights:
            return

        for height in heights:
            if height < 0:
                raise ValueError("Histogram heights must be non-negative.")


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        """LeetCode entry point."""
        analyzer = HistogramAnalyzer()
        return analyzer.largest_rectangle_area(heights)

Why this works

The stack is always kept in increasing-height order. That invariant means any bar still on the stack has not yet seen a smaller bar to its right.

Once the current bar is shorter than the stack top, the stack top can no longer extend past the current index. So its first smaller bar on the right is known exactly now.

At the same time, after popping it, the new stack top is the nearest strictly smaller bar on the left, because every taller or equal-height bar between them has already been removed.

That is enough information to compute the popped bar’s widest valid rectangle. Since every bar is finalized exactly once, the algorithm is both correct and linear.

Complexity

  • Time: O(n) because each index is pushed once and popped once
  • Space: O(n) for the monotonic stack in the worst case

Interview follow-ups

What if the interviewer wants the rectangle boundaries, not just the area?

The core algorithm barely changes. When a bar is popped, the solution already knows its full rectangle span: the left boundary is one position to the right of the new stack top, and the right boundary is one position to the left of the current index. So instead of tracking only the best area, the implementation can also remember the corresponding left, right, and height.

That variant still runs in O(n) time and O(n) space. The main difference is that tie-breaking must be defined clearly if multiple rectangles share the same area. In an interview, it is worth stating that the data is already available inside the stack method, so returning boundaries is an output-format change, not a fundamentally harder algorithm.

What if each bar has a variable width instead of width 1?

Then the simple formula right - left + 1 no longer gives the rectangle width. The monotonic-stack idea still works, but the width of a span must be computed from prefix sums of the actual bar widths. In other words, the popped bar still represents the limiting height over some contiguous range, but the range width is now the sum of the bars’ widths rather than the number of bars.

The expected solution is to precompute prefix sums of widths so any span width can be queried in O(1), then reuse the same nearest-smaller-boundary logic. That keeps the total runtime at O(n) with O(n) extra space. The tradeoff is slightly more bookkeeping, but the structural insight remains exactly the same.

How would you extend this idea to the maximal rectangle problem in a binary matrix?

That is the classic follow-up because the matrix problem can be reduced to a sequence of histogram problems. Treat each row as the base of a histogram where the height at each column is the number of consecutive 1s ending at that row. For every row, update those heights and run the same histogram algorithm on the updated row.

If the matrix has rows by cols, this gives O(rows * cols) time, because each row triggers one linear histogram pass over the columns. The tradeoff is that the histogram algorithm becomes a reusable subroutine inside a larger loop. This is a strong interview answer because it shows the candidate understands the monotonic-stack pattern deeply enough to transfer it to a harder-looking problem.

Could you solve it with divide and conquer instead of a stack?

Yes, but it is usually not the best final answer. A divide-and-conquer approach can pick the minimum bar in a range, use it as one candidate rectangle over the entire range, then recurse on the left and right subranges. That logic is correct, because the optimal rectangle either spans the whole range using the minimum height or lies entirely in one side.

The drawback is efficiency. If the minimum is found naively each time, the runtime can degrade to O(n^2). With stronger data structures such as a range minimum query structure, it can be improved, but the solution becomes more complicated than necessary. For the standard LeetCode version, the monotonic stack is preferred because it reaches O(n) time with much less machinery.