How Do You Solve Largest Rectangle in Histogram?
Learn the monotonic stack solution to largest rectangle in histogram, its O(n) complexity, and how to explain it in interviews.
Expected Interview Answer
The largest rectangle in histogram problem finds the maximum-area rectangle that fits under a sequence of bars, solved optimally in O(n) time using a monotonic increasing stack of bar indices instead of the O(n^2) brute-force approach of checking every pair of bars.
The stack holds indices of bars with increasing heights. When a shorter bar is encountered, it means every taller bar still on the stack can never extend further right, so those taller bars are popped off one at a time and each one’s maximum rectangle is finalized: its height times a width spanning from the new top of the stack (exclusive) to the current index (exclusive). This works because the popped bar’s rectangle is bounded on the right by the current shorter bar and on the left by the next-shorter bar still remaining on the stack. Each bar is pushed once and popped at most once, giving amortized O(n) time despite the nested-looking logic. A sentinel bar of height 0 appended at the end forces any remaining bars on the stack to be resolved.
- O(n) time versus O(n^2) brute force over every bar pair
- O(n) space for the stack in the worst case
- Each bar is pushed and popped at most once, giving true linear amortized cost
- The same monotonic stack pattern solves next-greater-element style problems
AI Mentor Explanation
Imagine a row of stumps of varying heights set up for a trick-shot photo, and a photographer wants the largest rectangular banner that fits entirely under the stump line without poking above any stump. The photographer keeps a running list of stump indices with increasing heights; when a shorter stump appears, every taller stump still on the list can never stretch further right, so each is popped and its best possible banner is measured using the gap between the current shorter stump and whatever stump remains on the list before it. Each stump is added and removed from the list exactly once, so the whole banner-fitting process finishes in linear time. This trick — resolving tall stumps the moment a shorter one appears — avoids comparing every pair of stumps directly.
Step-by-Step Explanation
Step 1
Maintain a monotonic increasing stack
Push bar indices onto a stack only while their heights stay increasing.
Step 2
Pop and resolve on a shorter bar
When a shorter bar appears, pop taller bars one by one since they can never extend past this point.
Step 3
Compute width from stack neighbors
Each popped bar’s width spans from the new stack top (exclusive) to the current index (exclusive).
Step 4
Flush with a sentinel
Append a height-0 sentinel bar at the end to force any remaining stacked bars to be resolved.
What Interviewer Expects
- Explain why a monotonic increasing stack is the right structure, not a simple scan
- Correctly derive the width formula using the stack’s new top after popping
- State the O(n) amortized time complexity and justify it (each index pushed/popped once)
- Mention the brute-force O(n^2) alternative as a baseline comparison
Common Mistakes
- Computing width incorrectly by forgetting the new stack top after a pop
- Forgetting the sentinel bar, leaving bars unresolved on the stack at the end
- Assuming O(n^2) nested loops are unavoidable without recognizing the stack approach
- Confusing this with maximal square/rectangle in a binary matrix, a related but distinct problem
Best Answer (HR Friendly)
“This problem asks for the biggest rectangle you can fit under a row of bars of different heights. I solve it with a stack that keeps bar indices in increasing height order, and whenever a shorter bar shows up, I resolve all the taller bars still on the stack because I now know exactly how far right they could have stretched.”
Code Example
def largest_rectangle_area(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_areaFollow-up Questions
- How would you extend this to solve the maximal rectangle problem in a binary matrix?
- Why does each bar get pushed and popped at most once, giving amortized O(n) time?
- How would you also return the coordinates of the optimal rectangle, not just its area?
- What happens if the histogram contains bars of height zero?
MCQ Practice
1. What kind of stack is used to solve largest rectangle in histogram efficiently?
The stack holds bar indices in increasing height order, so a shorter bar triggers resolving taller bars.
2. What is the overall time complexity of the stack-based solution?
Each index is pushed once and popped at most once, giving amortized O(n) total work.
3. When a bar is popped from the stack, how is its rectangle width computed?
The popped bar is bounded on the left by the new stack top and on the right by the current shorter bar.
Flash Cards
What data structure solves largest rectangle in histogram in O(n)? — A monotonic increasing stack of bar indices.
When is a bar popped from the stack? — When the current bar is shorter than the height at the top of the stack.
How is the width of a popped bar’s rectangle computed? — From the new stack top (exclusive) to the current index (exclusive).
Why is a sentinel height-0 bar appended at the end? — To force any bars still left on the stack to be popped and resolved.