Introduction

The largest-rectangle-in-a-histogram problem asks for the maximum area that can be formed by contiguous bars in a histogram. The brute-force solution is easy to understand, but the classic stack-based algorithm is the one worth learning because it reduces the running time to linear time.

Problem Setup

Given an array of bar heights, each bar has width 1. A rectangle can span several adjacent bars, but its height is limited by the shortest bar in that span.

For example, in:

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

the largest rectangle has area 10, formed by bars with heights 5 and 6, using width 2.

Brute Force Approach

The naive solution checks every possible start and end position and tracks the minimum height within that range.

1def largest_rectangle_bruteforce(heights):
2    best = 0
3
4    for left in range(len(heights)):
5        min_height = heights[left]
6        for right in range(left, len(heights)):
7            min_height = min(min_height, heights[right])
8            width = right - left + 1
9            best = max(best, min_height * width)
10
11    return best
12
13
14print(largest_rectangle_bruteforce([2, 1, 5, 6, 2, 3]))

This works, but it is O(n^2), which becomes too slow for large inputs.

Linear-Time Stack Algorithm

The efficient solution uses a monotonic increasing stack of indices. The key idea is:

• push indices while heights keep increasing
• when a lower bar appears, pop taller bars
• for each popped bar, compute the largest rectangle where that bar is the limiting height

1def largest_rectangle_area(heights):
2    stack = []
3    max_area = 0
4    extended = heights + [0]
5
6    for i, height in enumerate(extended):
7        while stack and extended[stack[-1]] > height:
8            top = stack.pop()
9            h = extended[top]
10
11            if stack:
12                width = i - stack[-1] - 1
13            else:
14                width = i
15
16            max_area = max(max_area, h * width)
17
18        stack.append(i)
19
20    return max_area
21
22
23print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))

10

The extra trailing 0 forces the stack to empty at the end so all remaining candidate rectangles are evaluated.

Why the Stack Works

When you pop an index from the stack, you have just discovered the first bar to the right that is shorter than the popped bar. The new top of the stack tells you the first bar to the left that is shorter. That means you now know the full width over which the popped height is the minimum.

That is the central trick. Each bar is pushed once and popped once, so the total work is O(n).

Walking Through One Example

Take heights = [2, 1, 5, 6, 2, 3].

• push index 0 because the stack is empty
• at index 1, height 1 is lower than 2, so pop 0 and compute area 2 * 1
• push 1
• push 2 and 3 because 5 then 6 keeps increasing
• at index 4, height 2 is lower than 6, so pop 3, then pop 2
• those pops reveal the rectangle of height 5 and width 2, area 10

Once you see that a pop means "we now know the right boundary", the algorithm becomes much easier to reason about.

When This Pattern Reappears

This problem is also a building block for other tasks, especially finding the largest rectangle of 1s in a binary matrix. In that setting, each row is treated as the base of a histogram, and the same stack algorithm is applied repeatedly.

That is why this problem shows up often in interviews and algorithm practice. It teaches a reusable monotonic-stack technique, not just one isolated solution.

Common Pitfalls

• Forgetting to flush the stack at the end. Appending a trailing 0 is the usual fix.
• Using bar heights instead of indices in the stack. You need indices to compute widths correctly.
• Miscomputing the width after a pop. The width depends on the current index and the new stack top.
• Assuming the brute-force approach is "good enough" for large inputs. It degrades quickly on long arrays.
• Losing sight of what a pop means. A pop marks the moment when both left and right boundaries are known for that height.

Summary

• The brute-force solution checks all spans and runs in quadratic time.
• The standard efficient solution uses a monotonic increasing stack of indices.
• Each popped bar defines a rectangle whose width is known from the nearest smaller bars on both sides.
• The linear-time algorithm runs in O(n) because each index is pushed and popped once.
• This same stack pattern appears in several other range and matrix problems.