Largest Rectangle in Histogram: The Monotonic Stack in O(n)

Largest rectangle in a histogram is the problem where the monotonic stack stops being a trick for "next greater element" and becomes a real tool. The brute force is easy and quadratic. The linear solution is ten lines, and every one of them is doing something specific.

The problem it solves

You get bar heights, each bar one unit wide, for example [2, 1, 5, 6, 2, 3]. Find the area of the largest axis-aligned rectangle that fits under the bars. Here it is 10: height 5 across the bars 5 and 6.

A rectangle's height is limited by the shortest bar it covers. So every candidate rectangle can be described by one bar: the shortest bar inside it, stretched as far left and right as possible before hitting something shorter. The answer is the best of those n candidates.

The intuition

For each bar you need two walls: the nearest shorter bar on the left and the nearest shorter bar on the right. The rectangle for that bar spans everything strictly between them.

A stack whose heights only increase from bottom to top finds both walls in one sweep:

• A bar taller than the top of the stack is pushed. Its right wall has not appeared yet; the rectangle could still grow.
• A bar shorter than or equal to the top pops it. The arriving bar is the popped bar's right wall.
• After the pop, the bar now on top of the stack is the popped bar's left wall: everything between them was taller, or it would not have been popped earlier. If the stack is empty, the rectangle reaches all the way to index 0.

So each pop measures one rectangle: height * (right - left), where left is one past the left wall.

Bars still on the stack at the end never met a right wall. Appending a 0 to the heights fixes that: it is shorter than every bar, so it pops everything that is left.

Watch it run

The animation sweeps [2, 1, 5, 6, 2, 3]. Bars 1, 5 and 6 wait on the stack. When the second 2 arrives it pops 6, width 1, area 6, and then 5, width 2, area 10. The trailing zero flushes 3, then 2 with width 4, then 1 with width 6. Every bar is pushed once and popped once, and the winner is area 10.

The code

The stack version, and a brute force that checks every range while tracking its minimum:

def largest_rectangle(heights):
    stack, best = [], 0                      # indexes; heights increase upwards
    for i, h in enumerate(heights + [0]):    # the 0 is shorter than every bar
        while stack and heights[stack[-1]] >= h:
            top = heights[stack.pop()]       # i is its right wall
            left = stack[-1] + 1 if stack else 0   # the bar below is its left wall
            best = max(best, top * (i - left))
        stack.append(i)
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))   # 10
print(largest_rectangle([2, 4]), largest_rectangle([]), largest_rectangle([4, 4, 4]))   # 4 0 12

def largest_rectangle_brute(heights):
    best = 0
    for i in range(len(heights)):
        low = heights[i]
        for j in range(i, len(heights)):     # every range i..j, tracking its minimum
            low = min(low, heights[j])
            best = max(best, low * (j - i + 1))
    return best

The classic follow-up is the largest rectangle of 1s in a binary matrix. Treat each row as the floor of a histogram, where a column's height is the number of consecutive 1s ending in that row, and run the same function once per row:

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

grid = [[1, 0, 1, 0, 0],
        [1, 0, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0]]
print(maximal_rectangle(grid))               # 6

Both against brute force on random inputs, with zeros and repeated heights included on purpose:

import random

def maximal_rectangle_brute(grid):
    rows, cols, best = len(grid), len(grid[0]), 0
    for r1 in range(rows):
        for r2 in range(r1, rows):
            for c1 in range(cols):
                for c2 in range(c1, cols):
                    if all(grid[r][c] for r in range(r1, r2 + 1) for c in range(c1, c2 + 1)):
                        best = max(best, (r2 - r1 + 1) * (c2 - c1 + 1))
    return best

random.seed(15)
ok = True
for _ in range(1000):
    h = [random.randint(0, 8) for _ in range(random.randint(0, 12))]
    ok &= largest_rectangle(h) == largest_rectangle_brute(h)
for _ in range(200):
    g = [[random.randint(0, 1) for _ in range(random.randint(1, 5))]]
    g += [[random.randint(0, 1) for _ in g[0]] for _ in range(random.randint(0, 4))]
    ok &= maximal_rectangle(g) == maximal_rectangle_brute(g)
print(ok)                                    # True

The complexity

• Brute force checks every range i..j with a running minimum: O(n^2) time, O(1) space.
• The stack pushes each index once and pops it at most once, so the inner while runs at most n + 1 times across the whole sweep, not per bar. That is O(n) time and O(n) space for the stack.
• The matrix follow-up runs one O(cols) histogram per row: O(rows * cols) overall, which is linear in the size of the grid.

Where it goes wrong

• Forgetting the sentinel. Without the trailing 0, an increasing input like [1, 2, 3] never pops anything and the answer comes out as 0.
• Computing the width from the popped index. The left edge comes from the bar now under the popped one, not from the popped bar's own index; earlier, taller bars were already popped from between them.
• Worrying about equal heights. Popping on >= means an equal bar ends its twin's rectangle early, but the last bar of the run is measured with the full width, so the answer is unaffected. The random check includes plenty of ties.
• Storing heights instead of indexes. The width needs positions; store indexes and look the heights up.

How to say it in an interview

"Every rectangle is determined by its shortest bar, so for each bar I want the nearest shorter bar on each side. I keep a stack of indexes with increasing heights. When a bar is shorter than the top, it's the top's right wall; I pop, and the new top is the left wall, so the area is height times i - wall - 1, or i if the stack is empty. A zero appended at the end flushes the stack. Each index is pushed and popped once, so it's O(n) time and O(n) space. The binary-matrix version runs this on each row's column heights."

The stack itself is introduced in the monotonic stack, and monotonic stack explained covers the simpler next-greater-element problems it grows from.