Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Largest Rectangle in Histogram

LeetCode #84Hard
Increasing stack · shorter bars close rectangles

Given an array of bar heights representing a histogram where each bar has width 1, return the area of the largest rectangle that can be formed within the histogram.

Asked atAmazonGoogleMicrosoft
step 1 / 24
1
2
3
4
5
6
2
1
5
6
2
3
[0][1][2][3][4][5]
Brute force · grow each bar both ways
▸
1given h[]
2best ← 0
3for i ← 0 to n − 1:
4    grow l, r while neighbors ≥ h[i]
5    best = max(best, h[i] × (r − l + 1))
6return best
state
  • n6

line 1Largest rectangle fully inside the bars. Key observation: any candidate rectangle is capped by its SHORTEST bar. So: for each bar, grow left and right while neighbors are at least as tall.