DSA Largest Rectangle in a Histogram

The problem

A histogram is a row of bars, each of width one, with given heights. A rectangle inside the histogram spans a run of neighbouring bars, and its height is the shortest bar in that run. The problem asks for the largest area any such rectangle can reach.

The area of a rectangle is its height times its width. The cases below are the ones this article uses throughout. An empty histogram answers 0.

cases = [
    ([2, 1, 5, 6, 2, 3], 10),
    ([4, 2, 0, 3, 2, 5], 6),
    ([3, 3, 3], 9),
    ([5], 5),
    ([], 0),
]
for heights, expected in cases:
    print("heights", heights, "-> largest area:", expected)

Read one row at a time. In the first row, the winning rectangle has height 5 and width 2. In the second row, a bar of height 0 splits the histogram into two separate parts.

Intuition: stretch one bar as far as it reaches

The first idea picks one bar and stretches it left and right. The stretch stops at the first shorter bar on each side. Every bar inside the stretch is at least as tall as the picked bar, so the full stretch is one legal rectangle.

heights = [2, 1, 5, 6, 2, 3]
i = 4
height = heights[i]
left = i
while left - 1 >= 0 and heights[left - 1] >= height:
    left -= 1
right = i
while right + 1 < len(heights) and heights[right + 1] >= height:
    right += 1
width = right - left + 1
print("height:", height, "from index", left, "to index", right)
print("width:", width, "area:", height * width)

The bar of height 2 stretches across four bars before the bar of height 1 stops it on the left. Its area is 8, close to the best of 10. The trap is doing this stretch separately for every bar, because each stretch rescans bars its neighbours already scanned.

Brute force: measure every span

The brute force tries every span of bars. For each left edge it extends the right edge one bar at a time, tracking the shortest height seen. Each span gives one candidate area.

A counter records how many spans were measured. The span count is the honest cost of the method, and it grows with the square of the bar count.

def largest_brute(heights):
    best = 0
    spans = 0
    for left in range(len(heights)):
        shortest = None
        for right in range(left, len(heights)):
            h = heights[right]
            shortest = h if shortest is None else min(shortest, h)
            spans += 1
            area = shortest * (right - left + 1)
            if area > best:
                best = area
    return best, spans

best, spans = largest_brute([2, 1, 5, 6, 2, 3])
print("largest:", best)
print("spans measured:", spans)
best, spans = largest_brute([4, 2, 0, 3, 2, 5])
print("second case largest:", best)
print("spans measured:", spans)

Six bars hold 21 spans, and every one is measured. Doubling the bars roughly quadruples the span count. The optimal solution finds each bar's full stretch without measuring the spans in between.

The optimal solution: a rising stack closed by zero sentinels

A stack holds bars in rising height order, and a shorter arrival pops each taller bar and closes its span between the new left boundary and the arrival. That one sentence is the whole method.

A sentinel is an extra bar of height zero placed at an end. Zero sentinels at both ends close every span. The final sentinel is shorter than every real bar, so it flushes the stack and every bar receives its span.

When a bar pops, the bar under it on the stack is its left boundary. The width runs from that boundary to the arriving bar, minus one. Equal bars follow one fixed rule here, because the pop test is strictly taller than the arrival.

def largest(heights):
    padded = [0] + heights + [0]
    stack = []
    best = 0
    for i, h in enumerate(padded):
        while stack and padded[stack[-1]] > h:
            j = stack.pop()
            height = padded[j]
            left = stack[-1]
            width = i - left - 1
            area = height * width
            if area > best:
                best = area
        stack.append(i)
    return best

cases = [
    ([2, 1, 5, 6, 2, 3], 10),
    ([4, 2, 0, 3, 2, 5], 6),
    ([3, 3, 3], 9),
    ([5], 5),
    ([], 0),
]
for heights, expected in cases:
    result = largest(heights)
    print("heights", heights, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass. The zero bar inside the second case closes the spans on its left at once. Bars after it start fresh spans of their own.

Walkthrough: closing spans in [2, 1, 5, 6, 2, 3]

The walk runs the stack method on the main case. Each line prints when one bar pops and its span closes. The best area updates as the spans close.

def largest_traced(heights):
    padded = [0] + heights + [0]
    stack = []
    best = 0
    for i, h in enumerate(padded):
        while stack and padded[stack[-1]] > h:
            j = stack.pop()
            height = padded[j]
            left = stack[-1]
            width = i - left - 1
            area = height * width
            print("bar", height, "span", width, "area", area)
            if area > best:
                best = area
        stack.append(i)
    return best

print("largest:", largest_traced([2, 1, 5, 6, 2, 3]))

The bar of height 5 closes with width 2 and area 10, the answer. The bar of height 1 closes last, with the full width of 6. Its height is so small that the wide span still loses.

Complexity

The brute force measures n times n plus 1, divided by 2, spans for n bars, so its time is O(n^2). The stack pushes each padded bar once and pops each at most once, so its time is O(n).

The brute force stores only its running values, so its extra space is O(1). The padded list and the stack each hold at most one entry per bar, so their space is O(n).

def stack_work(heights):
    padded = [0] + heights + [0]
    stack = []
    pushes = 0
    pops = 0
    for i, h in enumerate(padded):
        while stack and padded[stack[-1]] > h:
            stack.pop()
            pops += 1
        stack.append(i)
        pushes += 1
    return pushes + pops

for n in (6, 12, 24):
    heights = [(i * 7) % 9 + 1 for i in range(n)]
    spans = n * (n + 1) // 2
    print("bars", n, "- brute spans:", spans, " stack pushes + pops:", stack_work(heights))

At 24 bars the span count is 300 against fewer than 52 stack moves. The stack pays once per bar, however the heights are arranged.

Edge cases and pitfalls

Forgetting the final sentinel is the classic mistake. Without it, bars still on the stack at the end never close their spans. A rising histogram would then report only the small early rectangles.

An off-by-one width is the second mistake. The width excludes both boundaries, so it subtracts one after the gap between indices. Counting a boundary bar into the span inflates every area.

def largest(heights):
    padded = [0] + heights + [0]
    stack = []
    best = 0
    for i, h in enumerate(padded):
        while stack and padded[stack[-1]] > h:
            j = stack.pop()
            height = padded[j]
            left = stack[-1]
            width = i - left - 1
            area = height * width
            if area > best:
                best = area
        stack.append(i)
    return best

print("empty:", largest([]))
print("one bar:", largest([5]))
print("all equal:", largest([3, 3, 3]))
print("falling bars:", largest([5, 4, 3, 2, 1]))
print("zero bar in the middle:", largest([2, 0, 2]))

The falling row peaks at height 3 across three bars, for an area of 9. The zero bar splits its row into two single bars, and neither side can stretch across it.