Largest Rectangle in Histogram

Before we start

This is one of the most celebrated stack problems in competitive programming. It looks like a geometry puzzle but the core insight is pure monotonic stack from Chapter 5.01 — applied twice (left boundary and right boundary) simultaneously. Mastering this problem unlocks the matrix variant as a free bonus. By the end you will be able to:

• Explain what "this bar as the height" means and how that frames the problem.
• Write the O(n) single-pass stack solution from memory.
• Extend the solution to Maximal Rectangle in a Binary Matrix (LC #85).

Picture this first (no code yet)

The actual problem

Largest Rectangle in Histogram (LC #84):

Given an array heights of non-negative integers representing histogram bar widths of 1, find the area of the largest rectangle that can be formed within the histogram.

heights = [2, 1, 5, 6, 2, 3] → answer is 10 (bars at index 2 and 3, height 5, width 2).

First, the slow way (so you feel the pain)

O(n²) brute force: for each pair (i, j), the rectangle height is min(heights[i..j]) and width is j - i + 1. Enumerate all pairs and track the max area.

n = len(heights)
max_area = 0
for i in range(n):
    min_h = heights[i]
    for j in range(i, n):
        min_h = min(min_h, heights[j])
        max_area = max(max_area, min_h * (j - i + 1))

For n = 100,000: 10¹⁰ operations. At 10⁸ ops/sec, that is 100 seconds. The stack solution does it in O(n).

The turning point

The one idea to remember

The code (single-pass with sentinel)

def largestRectangleArea(heights):
    heights = heights + [0]   # sentinel: forces all remaining bars to pop at the end
    stack   = [-1]            # sentinel: gives a clean left boundary for leftmost bars
    max_area = 0

    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            height = heights[stack.pop()]   # this bar's height
            width  = i - stack[-1] - 1      # right = i, left = new stack top + 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Line-by-line narration:

1. heights + [0] — appending a zero sentinel ensures every bar eventually gets popped (a height-0 bar is shorter than everything). Without it, bars remaining in the stack at loop's end wouldn't be processed.
2. stack = [-1] — index −1 is a left sentinel. When we pop the leftmost bar, stack[-1] is −1, making width = i - (-1) - 1 = i, which spans from index 0 to i−1 correctly.
3. while heights[stack[-1]] >= h: — pop all bars taller than or equal to the arriving bar (if equal, we pop too — it is safe; those bars would form at most the same rectangle with the current bar extending it).
4. height = heights[stack.pop()] — the popped bar's height is the rectangle's height.
5. width = i - stack[-1] - 1 — after popping, stack[-1] is the new top = the previous-smaller index. The width spans from stack[-1] + 1 to i - 1, so width = i - stack[-1] - 1.
6. stack.append(i) — push current bar's index (stack stays increasing in height).

Watch it happen, frame by frame

heights = [2, 1, 5, 6, 2, 3] → appended sentinel: [2, 1, 5, 6, 2, 3, 0]

stack=[-1]

i=0, h=2: stack top=-1 (sentinel). Push 0.  stack=[-1, 0]
i=1, h=1: heights[0]=2 >= 1 → pop 0.
           height=2, width=1-(-1)-1=1. area=2. max=2.
           stack top=-1. Push 1.  stack=[-1, 1]
i=2, h=5: 1<5 → push 2.  stack=[-1,1,2]
i=3, h=6: 5<6 → push 3.  stack=[-1,1,2,3]
i=4, h=2: heights[3]=6>=2 → pop 3. height=6, width=4-2-1=1. area=6. max=6.
           heights[2]=5>=2 → pop 2. height=5, width=4-1-1=2. area=10. max=10. ✅
           heights[1]=1 < 2 → stop. Push 4.  stack=[-1,1,4]
i=5, h=3: heights[4]=2<3 → push 5.  stack=[-1,1,4,5]
i=6, h=0 (sentinel):
           heights[5]=3>=0 → pop 5. height=3, width=6-4-1=1. area=3.
           heights[4]=2>=0 → pop 4. height=2, width=6-1-1=4. area=8.
           heights[1]=1>=0 → pop 1. height=1, width=6-(-1)-1=6. area=6.
           stack=[-1]. Top=-1, stop. Push 6. (doesn't matter)

max_area = 10  ✅

Extension: Maximal Rectangle in Binary Matrix (LC #85)

Given an m × n binary matrix, find the area of the largest rectangle containing only 1s.

Reduction: treat each row as the "ground" and compute a histogram of consecutive 1s above each cell. Then run LC #84 on each row's histogram.

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    n        = len(matrix[0])
    heights  = [0] * n
    max_area = 0

    for row in matrix:
        # update histogram
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0

        # largest rectangle for this row's histogram
        max_area = max(max_area, largestRectangleArea(heights))

    return max_area

For an m × n matrix: O(m × n) time — one histogram update per cell, one stack pass per row.

Common traps

def largestRectangleArea(heights):
    heights  = heights + [0]   # sentinel forces all pops
    stack    = [-1]            # sentinel for left boundary
    max_area = 0
    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            ht       = heights[stack.pop()]
            wd       = i - stack[-1] - 1
            max_area = max(max_area, ht * wd)
        stack.append(i)
    return max_area

Check yourself

Practice problems

Next up: Stack-based Expression Evaluation — how stacks handle operator precedence and parentheses to evaluate arithmetic expressions in O(n), covering Reverse Polish Notation and Basic Calculator.