Largest Rectangle in Histogram
Use a monotonic stack to track left boundaries and compute the maximum area rectangle that fits within a histogram in a single pass.
Problem: Largest Rectangle in Histogram
The Largest Rectangle in Histogram problem (LeetCode 84) gives an array of non-negative integers representing bar heights in a histogram where each bar has width 1. Find the area of the largest rectangle that can be formed within the histogram. The rectangle must span contiguous bars and its height is limited by the shortest bar it covers.
A brute-force approach: for every pair (i, j), compute the minimum height in [i, j] and multiply by (j - i + 1). This is O(n³) or O(n²) with pre-computed minimums — too slow. The monotonic stack solution runs in O(n).
# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')
# Brute force for small inputs:
def brute_force(heights):
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))
return max_area
print('Brute force answer:', brute_force(heights)) # 10Key Insight: What Limits Each Bar's Rectangle?
For each bar i with height h, the largest rectangle it can be the minimum of extends: leftward until the first bar shorter than h, and rightward until the first bar shorter than h. The width is right_boundary - left_boundary - 1 and the area is h × width.
This reframes the problem: for each bar, find its previous smaller element (PSE) and next smaller element (NSE). These are exactly what a monotonic increasing stack computes. The moment we pop bar i (because a shorter bar was found), the current bar is its NSE and the stack top after popping is its PSE.
heights = [2, 1, 5, 6, 2, 3]
n = len(heights)
# Find PSE and NSE for each bar
pse = [-1] * n # index of previous smaller element
nse = [n] * n # index of next smaller element (default: beyond array)
# PSE
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
# NSE
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = nse[i] - pse[i] - 1
area = heights[i] * width
print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
max_area = max(max_area, area)
print('Max area:', max_area)