Largest Rectangle in Histogram
A histogram is a row of bars standing side by side with no gaps, each one unit wide: heights[i] is the height of bar i. A rectangle inside it covers a run of neighbouring bars and can be no taller than the shortest bar in that run.
Return the largest area such a rectangle can have.
Function
- heightsinteger-array
- the height of each bar, from left to right
- Returnsinteger
- the area of the largest rectangle that fits in the histogram
Constraints
1 ≤ heights.length ≤ 2 × 1040 ≤ heights[i] ≤ 105- Every bar is one unit wide, so a rectangle over bars
itojisj-i+1units wide.
Examples
- Input
- heights = [2, 5, 6, 3, 4, 1]
- Output
- 12
- Explanation
- The bars 5, 6, 3 and 4 are all at least 3 tall, so a rectangle of height 3 spans them: 3 × 4 = 12. The two tallest bars only give 5 × 2 = 10.
- Input
- heights = [1, 8, 1, 1]
- Output
- 8
- Explanation
- The bar of 8 alone makes 8 × 1 = 8. Any wider rectangle includes a bar of 1, so it is at most 1 × 4 = 4.
- Input
- heights = [3, 3, 3, 3]
- Output
- 12
- Explanation
- All four bars are 3 tall, so the whole histogram is one rectangle: 3 × 4 = 12.
Follow-up
Suppose each bar has its own width, given in a second array. What changes in the one-pass stack solution?
Hints
Open them one at a time. Each one gives away a little more.
The largest rectangle touches the top of at least one bar under it: if it did not, you could make it taller. So try every bar as the bar that sets the height. How wide can a rectangle exactly that tall get?
A rectangle as tall as bar
ispreads left and right until it meets a strictly shorter bar on each side. If you know the nearest shorter bar on each side of every bar, each bar gives one candidate area, and there are onlynof them.Keep a stack of indices whose heights rise from bottom to top. When a bar arrives that is not taller than the top, the top bar cannot reach any further right: pop it, and its rectangle covers the bars strictly between the new top of the stack and the current bar. A bar of height 0 after the end pops whatever is left.
Solution
Trying every run of bars costs about n²/2 steps. Turn it around: the best rectangle is exactly as tall as one of its bars, so each bar only needs to know how far it spreads before a shorter bar stops it. A monotonic stack finds those points in O(n).
Try every run with a running minimum
Correct, but does not finish on the largest tests
Intuition
Fix start, grow end one bar at a time, and keep the lowest height seen so far. The best rectangle over that run has area lowest × (end-start+1). Starting at the 5 in [2, 5, 6, 3, 4, 1], the runs give 5, 10, 9, 12 and 5.
It is correct because every rectangle sits over some run and can be no taller than that run's lowest bar. It is slow because there are n(n+1)/2 runs: about 2 × 10^8 for 2 × 10^4 bars.
Algorithm
- Set
bestto 0. - For each
start, setlowesttoheights[start]. - For each
endfromstartto the last bar, lowerlowesttoheights[end]if that bar is shorter. - Update
bestwithlowest × (end-start+1). - Return
best.
def largestRectangleArea(heights):
n = len(heights)
best = 0
for start in range(n):
lowest = heights[start]
for end in range(start, n):
# The rectangle over start..end is as tall as the lowest bar in it.
lowest = min(lowest, heights[end])
best = max(best, lowest * (end - start + 1))
return bestNearest shorter bar on each side
Intuition
The best rectangle reaches the top of at least one bar under it; otherwise you could raise it. So for each bar i, take the rectangle exactly heights[i] tall that spreads until a strictly shorter bar on each side, at left[i] and right[i] (-1 and n when there is none). Its width is right[i]-left[i]-1.
To find left[i], walk left to right with a stack of indices whose heights rise. Bar i pops every bar at least as tall as itself: none of them can be the nearest shorter bar for i or any later bar, since i is closer and no taller. The top is then left[i]. A right-to-left pass gives right[i].
Each index is pushed and popped at most once per pass, so the time is O(n).
Algorithm
- Walk left to right with a stack. For each
i, pop while the top bar is at least as tall asheights[i]; setleft[i]to the top, or -1 if the stack is empty; pushi. - Walk right to left the same way for
right[i], withnfor an empty stack. - Return the largest
heights[i] × (right[i]-left[i]-1).
def largestRectangleArea(heights):
n = len(heights)
left = [-1] * n # index of the nearest shorter bar on the left, or -1
right = [n] * n # index of the nearest shorter bar on the right, or n
stack = [] # indices whose heights rise strictly from bottom to top
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
best = 0
for i in range(n):
# Bar i is the lowest bar of everything strictly between left[i] and right[i].
best = max(best, heights[i] * (right[i] - left[i] - 1))
return bestOne pass with a monotonic stack
Intuition
The left-to-right pass already meets every right boundary and throws it away. When bar i pops bar t, bar i is no taller, so the rectangle of t stops there. On the left it stops at below, the index now under t on the stack, or -1 if the stack is empty. Measure at the pop: heights[t] × (i - below - 1).
That left end is correct because every bar between an entry and the one under it was popped by the entry, directly or through a chain, so none is shorter than the entry. A closing bar of height 0 pops what is left. In the first example the 1 at index 5 pops the 3 at index 3, with index 0 under it: 3 × 4 = 12.
Popping an equal bar early is safe: the later bar inherits its left boundary and measures the full run.
Algorithm
- Start with an empty stack and
best = 0. - For
ifrom 0 ton, take the heightheights[i], or 0 wheni = n. - While the top bar is at least that tall, pop it as
tand updatebestwithheights[t] × (i - below - 1), wherebelowis the new top or -1. - Push
i. - Return
best.
def largestRectangleArea(heights):
n = len(heights)
stack = [] # indices whose heights rise strictly from bottom to top
best = 0
for i in range(n + 1):
current = heights[i] if i < n else 0 # a bar of 0 past the end empties the stack
while stack and heights[stack[-1]] >= current:
# Bar i stops the popped bar on the right; the bar below it stops it on the left.
height = heights[stack.pop()]
left = stack[-1] if stack else -1
best = max(best, height * (i - left - 1))
stack.append(i)
return best
Pitfalls and edge cases
- Forgetting the bars still on the stack. On
[1, 2, 3, 4, 5]nothing is popped inside the loop; without the closing 0 you return 0 instead of 9. - Measuring the width from the popped bar's own index. In the first example the 3 at index 3 spans indices 1 to 4;
i - tgives 2 instead of 4. - The wrong width when the stack is empty after a pop. It is
i: on[2, 1, 2]the 1 spans all three bars for an area of 3. - Popping only on
>in the two-pass version. On[3, 3, 3, 3]each bar then sees a width of 1, and you return 3 instead of 12.
Frequently asked questions3
What is the time complexity of Largest Rectangle in Histogram?
The monotonic stack solution runs in O(n) time and O(n) extra space: every index is pushed once and popped once. Trying every run of bars takes O(n²) time.
Can Largest Rectangle in Histogram be solved with divide and conquer?
Yes. The lowest bar of a range either sits under the best rectangle, which is then lowest × width, or splits the range into two parts you solve on their own. Scanning for the minimum makes this O(n log n) on random input and O(n²) on sorted input; a segment tree makes it O(n log n) always.
How is Largest Rectangle in Histogram used for the maximal rectangle in a 0/1 grid?
Go row by row and count, per column, the 1s stacked up to the current row; a 0 resets the count. Each row's counts form a histogram, and its largest rectangle is the largest rectangle of 1s ending on that row: O(rows × cols) time in all.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def largestRectangleArea(heights):
# Write code hereTest #1
Test #2
Test #3
Argument
heights = [2, 5, 6, 3, 4, 1]
Expected Output
12