Largest Rectangle in Histogram Using Stack

Given an array of bar heights representing a histogram, find the area of the largest rectangle that fits entirely within the histogram.

Why Stacks?

For each bar, the largest rectangle using that bar as the shortest bar extends left and right until a shorter bar is found. We need the Previous Smaller Element (PSE) and Next Smaller Element (NSE) for each bar — exactly what a monotonic stack computes.

Solution

def largest_rectangle_area(heights):
    """
    Find largest rectangle in histogram.
    Time: O(n), Space: O(n)
    """
    stack = []  # Indices of bars in increasing height order
    max_area = 0
    heights.append(0)  # Sentinel to flush remaining bars

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    heights.pop()  # Remove sentinel
    return max_area

Trace

Heights: [2, 1, 5, 6, 2, 3]

i=0, h=2: push → stack=[0]
i=1, h=1: pop 0(h=2), width=1, area=2   → stack=[1]
i=2, h=5: push → stack=[1,2]
i=3, h=6: push → stack=[1,2,3]
i=4, h=2: pop 3(h=6), width=1, area=6
           pop 2(h=5), width=2, area=10  ← MAX
           push → stack=[1,4]
i=5, h=3: push → stack=[1,4,5]
i=6, h=0: pop 5(h=3), width=1, area=3
           pop 4(h=2), width=4, area=8
           pop 1(h=1), width=6, area=6

Max area: 10

Without Sentinel (Explicit Cleanup)

def largest_rectangle_area_v2(heights):
    stack = []
    max_area = 0
    n = len(heights)

    for i in range(n):
        while stack and heights[stack[-1]] > heights[i]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    while stack:
        height = heights[stack.pop()]
        width = n if not stack else n - stack[-1] - 1
        max_area = max(max_area, height * width)

    return max_area

Why It Works

The stack maintains bars in increasing order of height. When a shorter bar arrives:

1. All taller bars in the stack can’t extend right anymore
2. For each popped bar, the width = distance between current index and the new stack top
3. This gives us the exact rectangle dimensions

Each bar is pushed once and popped once → O(n) total.

Common Pitfalls

1. Forgetting the cleanup — bars remaining in the stack after the loop need processing
2. Width calculation — when stack is empty after pop, width extends to the start (width = i)
3. Mutating input — the sentinel approach modifies the array; restore it or use a copy

Edge Cases

• All same heights — rectangle is n * h
• Ascending order — cleanup phase finds the answer
• Descending order — each bar triggers a pop immediately
• Single bar — area = heights[0]

When to Use This Pattern

The “find boundaries using monotonic stack” pattern solves many problems:

Related Problems

• Maximal Rectangle (LeetCode 85) — 2D version using this as subroutine
• Trapping Rain Water (LeetCode 42) — similar stack technique
• Sum of Subarray Minimums (LeetCode 907)
• Maximum Width Ramp (LeetCode 962)