Largest rectangle in a histogram

THE PROBLEM

“A capacity chart has adjacent bars of width one. Find the largest rectangular area that fits entirely beneath the bars, spanning a contiguous range. A tall bar alone may lose to a wide lower rectangle. When can you know that a candidate height cannot extend any farther right?”

Write this:

def largest_rectangle(heights):
    ...

Constructed practice question. Prerequisite: monotonic stacks. For a chosen contiguous range, the rectangle height is limited by its shortest bar. A stack can retain heights whose right boundary has not yet been discovered.

Contract	Required behavior
Input	Finite sequence of nonnegative integer heights; every bar width is one
Output	Maximum integer area under a contiguous interval
Boundaries	Empty/all-zero gives 0; equal-height bars may form one wider rectangle
Failure	Negative/noninteger heights raise `ValueError`; input unchanged
Scope	Area only; no witness coordinates or variable widths

Optional refresher · the underlying tool

For a histogram bar, the largest rectangle using that bar's height extends until a shorter bar stops it on each side. An increasing-height stack keeps starts unresolved:

heights = [2, 1, 2]
stack = [(0, 2)]  # (start index, height) for unresolved bars
start, height = stack.pop()  # at index 1, height 1 ends the 2-bar
print(height * (1 - start))  # 2: height 2 across width 1
stack.append((start, 1))    # height 1 can reach back to index 0

The best rectangle here has area 3 (height 1 across all three bars), not area 4. Flush remaining bars after the final input, often with a sentinel height 0.

A design choice worth saying aloud

Each stack entry means (earliest_start, height) for a bar that has not met a shorter right boundary. When a shorter bar arrives, carry the popped start backward before pushing the new height. A final zero-height sentinel closes all remaining rectangles; without it, increasing inputs leave candidates uncounted.

What the interviewer expects

The interviewer gives you the scenario and the contract above. Explain what a successful call returns, walk through one example below, and name what your state means before choosing a data structure.

Done means: Maximum integer area under a contiguous interval.

Now predict each output before looking at the reference; invalid input should leave any existing state unchanged unless the contract says otherwise.

Test-case scenarios to settle before coding

01 · Representative

Input / starting state: [2,1,5,6,2,3]
Expected result: 10

What it is testing: Height 5 across width 2 is best.

02 · Empty/all zero

Input / starting state: [] / [0,0]
Expected result: 0 / 0

What it is testing: No positive rectangle exists.

03 · Plateau

Input / starting state: [2,2,2]
Expected result: 6

What it is testing: Equal heights must combine across width.

04 · Zero split

Input / starting state: [2,0,2]
Expected result: 2

What it is testing: A zero ends positive rectangles.

05 · Final flush

Input / starting state: [1,2,3]
Expected result: 4

What it is testing: Remaining bars need a virtual right boundary.

06 · Invalid/atomic

Input / starting state: negative or noninteger height
Expected result: ValueError; input unchanged

What it is testing: Histogram geometry assumes nonnegative integers.

For each case, show which branch or state change produces that result.

[2,1,5,6,2,3] returns 10 from heights 5 and 6 over width two. [2,2,2] returns 6. [2,0,2] returns 2 because the zero breaks a positive rectangle. Ask whether the caller needs the left/right boundaries: save them with the winning area if so.

Diagram: Test-case scenarios to settle before coding

Implement the all-interval baseline if needed. Before reading the answer, determine which start index a new shorter height must inherit after popping taller bars.

Solution, boundaries, and follow-ups

The baseline considers every left boundary, extends right, and updates the minimum height; it costs O(n²) time and O(1) working state. Recomputing the minimum from scratch would unnecessarily increase this to O(n³). The linear solution changes the question from “what is each interval's minimum?” to “how far can this height remain the minimum?”

Maintain strictly increasing (earliest_start,height) pairs. On a lower incoming height, pop taller pairs and compute height × (current_index-start). Carry each popped start leftward so the incoming shorter height inherits the full span it can cover. Equal heights keep the older start rather than adding redundant pairs. Process one virtual zero-height bar after the real input to close all pending spans.

each retained height can cover every processed bar from its saved start through the previous position, and no smaller bar has yet ended that span. The first smaller bar fixes its maximal right boundary. Any optimal rectangle has a limiting minimum height; when that height is closed, the algorithm evaluates a rectangle at least as wide as the optimal interval.

Incoming position/height	Popped candidate	Area	Surviving start for incoming 2
4 / 2	start 3, height 6	6	3
4 / 2	start 2, height 5	10	2
End / virtual 0	pending spans	compare all	no retained positive height

Each pair is pushed once and popped once, giving O(n) total time and O(n) auxiliary space including the stack/input copy. A single position may pop O(n) pairs. The virtual sentinel is supplied by an iterator and never appended to the caller's list. Returning only area uses constant-size word-model output.

Follow-up 1 — bars have different widths. Predict two bars of heights [5,6] and widths [2,3]: the shared height-five rectangle has area 25. Replace index differences with cumulative horizontal coordinates. Keep the same height invariant but store each candidate's earliest x-coordinate.

Follow-up 2 — largest all-ones rectangle in a binary matrix. Treat each row as a histogram of consecutive ones ending at that row. Update heights (increment on one, reset on zero), then run this algorithm. Every rectangle has a bottom row, so O(rows × columns) time covers all possibilities with O(columns) working space.

Senior depth explains inherited start positions, equal-height handling, sentinel flush, and amortized cost. Lead depth clarifies numeric overflow and coordinate contracts when the chart becomes weighted or uses large physical dimensions.

Reference: solution.py (download file, source below); tests compare every short histogram over heights 0..2 with an independent interval oracle and check plateaus/flush behavior.

solution.py · solution.py

"""Largest rectangle under unit-width, nonnegative integer histogram bars."""
from itertools import chain


def largest_rectangle(heights):
    heights = list(heights)
    if any(not isinstance(height, int) or height < 0 for height in heights):
        raise ValueError("nonnegative integer heights required")
    best, stack = 0, []
    for index, height in enumerate(chain(heights, [0])):
        start = index
        while stack and stack[-1][1] > height:
            start, previous_height = stack.pop()
            best = max(best, previous_height * (index - start))
        if height and (not stack or stack[-1][1] < height):
            stack.append((start, height))
    return best

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/38-largest-histogram-rectangle -p 'test_*.py'