Largest Rectangle in Histogram
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given bar heights of a histogram (each bar width 1), find the area of the largest rectangle that fits inside it.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1For one bar, the best rectangle using its full height reaches left and right until a shorter bar appears.
- Hint 2Keep bars on a stack in increasing order; a shorter bar tells you the taller ones have found their right limit.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Skyline of buildings of different heights. The largest rectangular billboard you could hang is limited by its shortest building. Walk along the skyline keeping a stack of buildings that are still getting taller. When a SHORTER building appears, the taller buildings before it cannot extend any further right, so you finish them one by one: each finished building's billboard is as tall as it, as wide as the stretch back to the previous shorter building.
- The obvious way
For each bar expand left and right: O(n²).
- The key insight
Walk left to right with a stack of bar positions whose heights increase. When the next bar is shorter (or the end is reached), pop the top bar: it is finished. Its right limit is the current position; its left limit is the bar now on top of the stack (or the start if empty). Area = its height x the width between those limits. Add a zero-height bar at the end so everything gets popped.
- The algorithm
- Empty stack of bar positions; best area = 0. Add a height-0 bar at the end.
- For each bar: while the bar on the stack's top is taller or equal, pop it.
- For a popped bar: width = current position (if stack empty) else current position - new top - 1. Area = height x width; keep the best.
- Then put the current bar on the stack.
Watch it run
Exampleheights = [2, 1, 5, 6, 2, 3]
Bar 2 goes on the stack. Then bar 1 is shorter, so bar 2 is finished: it reaches left to the start, width 1, area 2. Bar 1 goes on the stack.
best 2
Where people slip
- When the stack becomes empty after popping, the bar extends all the way to the left edge (left limit -1).
- Pop on >= (not just >) so equal heights merge; either way the final answer is the same.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def largest_rectangle_area(heights):
stack = [] # positions of bars that keep rising
best = 0
for position, height in enumerate(heights + [0]): # the 0 bar finishes everything
while stack and heights[stack[-1]] >= height:
bar = heights[stack.pop()] # this bar can go no further right
left_limit = stack[-1] if stack else -1
width = position - left_limit - 1
best = max(best, bar * width)
stack.append(position)
return bestNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.