LeetCode 84 · Stack

Largest Rectangle in Histogram, explained with a picture

The biggest billboard on a skyline.

HardStack
▶ Watch it step by step

The problem

Each number is the height of a bar of width 1 in a histogram. Find the area of the largest rectangle that fits entirely inside the bars.

Input:  [2, 1, 5, 6, 2, 3]
Output: 10   (height 5 across the bars 5 and 6)

Picture it

Picture a city skyline and a billboard you want to paste flat against it. The billboard can be as tall as the shortest building it spans. We keep a stack of buildings in increasing height. When a shorter building arrives, taller buildings on the stack can’t stretch any further right, so we pop them and measure the biggest billboard each could support.

How to recognise it

  • You want the best contiguous range, and its value is (smallest item in the range) × (length of the range).
  • For each bar, the widest rectangle at exactly its height stretches until the nearest shorter bar on each side. "Nearest smaller element to the left and right" is the classic job of a monotonic stack (a stack kept in sorted order).
  • Up to 10^5 bars, so checking every range is too slow.

Start with brute force

Fix the left edge i, then move the right edge j outward while tracking the lowest bar seen so far. Each range's best rectangle is that minimum times the width.

def largest_brute(h):
    best = 0
    for i in range(len(h)):
        low = h[i]
        for j in range(i, len(h)):
            low = min(low, h[j])
            best = max(best, low * (j - i + 1))
    return best

There are about n²/2 ranges, each updated in O(1), so time is O(n²) and space is O(1). For n = 10^5 that is about 5 × 10^9 steps.

From brute force to the idea

  1. Find the waste. The best rectangle always has the height of some bar, and it spans the full stretch where that bar is the shortest. So only n candidates matter, one per bar, but the brute force tries n²/2 ranges.
  2. Ask where each bar's stretch ends. Bar k can extend right until the first shorter bar, and left until the first shorter bar before it.
  3. Keep a rising stack. Walk left to right with a stack of positions whose heights rise from bottom to top. Each bar on the stack is still waiting to learn where its stretch ends on the right.
  4. A lower bar closes stretches. When bar i with height x arrives, every stacked bar at least as tall as x cannot extend past i. Pop it: its right end is i - 1, and its left end is just after the bar now below it in the stack (stack[-1] + 1), or 0 if the stack is empty. Its area is height * (i - left).
  5. Flush with a sentinel. h + [0] adds a zero-height bar at the end, which pops everything still waiting. This builds a new list, so the caller's h is not changed.
  6. Equal heights are fine. With >=, equal bars pop each other and the earlier ones get too small a width, but the last of the run is measured across the whole run, so the maximum is still found.

This is the key idea: a rising stack tells each bar, at the moment it is popped, exactly how far it can stretch left and right.

The key idea

Monotonic increasing stack: when a bar is popped, the current index is its right limit and the new stack top is its left limit. O(n).

Python solution

def largest_rectangle(h):
    stack, best = [], 0          # positions with rising heights
    for i, x in enumerate(h + [0]):
        while stack and h[stack[-1]] >= x:
            height = h[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): every left edge with every right edgeO(1): a running minimum
Monotonic stack (shown code)O(n): each position is pushed once and popped onceO(n): the stack, plus the copy made by h + [0]

Edge cases

  • Empty list: returns 0 (only the sentinel is pushed). LeetCode promises at least one bar.
  • One bar ([4]): returns 4.
  • All equal ([3, 3, 3]): returns 9; the last 3 is popped by the sentinel with left edge 0.
  • Rising ([1, 2, 3, 4, 5]): nothing is popped until the sentinel arrives; returns 9 (height 3, width 3).
  • Falling ([5, 4, 3, 2, 1]): every bar is popped by the next one; returns 9.
  • Zero-height bars ([2, 0, 2]): the 0 splits the histogram; returns 2.

Common mistakes

  • Forgetting the sentinel. Bars still on the stack at the end are never measured, so [1, 2, 3] returns 0.
  • Measuring the width as i - popped_index. The rectangle also extends left of the popped bar, back to the bar below it in the stack.
  • Storing heights instead of positions on the stack, so the width cannot be computed.
  • Appending the sentinel with h.append(0), which changes the caller's list.
Your turn: largest rectangle of 1s in a grid

Given a grid of "0" and "1" cells, find the area of the largest rectangle made only of "1" cells. Describe your approach, then write it if you like.

Compare with our answer

Treat each row as the floor of a histogram. For every column, the bar height is the number of consecutive "1" cells ending at this row (reset to 0 on a "0"). Any all-ones rectangle has its bottom edge on some row, so the answer is the largest histogram rectangle over all rows.

def maximal_rectangle(grid):
    if not grid:
        return 0
    heights = [0] * len(grid[0])
    best = 0
    for row in grid:
        for c, cell in enumerate(row):
            heights[c] = heights[c] + 1 if cell == "1" else 0
        best = max(best, largest_rectangle(heights))
    return best

For R rows and C columns: time O(R · C), space O(C).

A strong answer mentions: how the heights are updated row by row, why every all-ones rectangle is found from its bottom row, and that it reuses the histogram routine unchanged.

Check what stuck

1. Given a list of daily rainfall, you must find the longest run of days multiplied by the lowest rainfall in that run. Which approach fits best?

2. When a bar is popped, why is its left edge stack[-1] + 1 rather than its own position?

3. A learner loops over enumerate(h) instead of enumerate(h + [0]). Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.