Interview Problem
Largest Rectangle in Histogram
“The Skyline Maximizer”
History
This problem is a rite of passage for anyone learning algorithm patterns. Interviewers love it because it quietly tests a lot of things at once:
- Can you see past the obvious O(n²) brute force?
- Do you recognize when a stack is the right tool for the job?
- Can you survive off-by-one errors without panicking?
Picture each bar as a building in a skyline. Your goal is to place the biggest possible rectangular billboard across those buildings. Every bar can be the height of a rectangle, but the real question is how wide it can stretch before something shorter ruins the party.
Problem Definition
You are given an array of non-negative integers. Each value represents the height of a histogram bar. Every bar has a width of exactly 1.
Your task is simple to state and painful to brute force:
Return the area of the largest rectangle that can be formed.
Core Idea
For every bar with height , imagine it being the shortest bar in a rectangle.
Now ask two questions: - How far can it extend to the left? - How far can it extend to the right?
Once you know that span, the area becomes straightforward.
For a bar at index with height :
Where: - is the index of the first shorter bar to the left, or if none exists - is the index of the first shorter bar to the right, or if none exists
The challenge is computing these bounds efficiently without scanning left and right for every bar.
How It Works
The monotonic stack keeps bar indices in increasing height order. Think of it as a memory structure that remembers where each bar started being valid. Whenever we encounter a bar that is shorter than the stack top, we have found a right boundary. That means it is time to calculate areas.
The Algorithm Step-by-Step
- Initialize an empty stack.
- Iterate through all bars.
- Add one extra virtual bar of height 0 at the end to force cleanup.
- For each bar:
- While the current bar is shorter than the bar at the top of the stack:
- Pop the stack.
- Compute the rectangle area using the popped bar as height.
- Update the maximum area.
- Push the current index onto the stack.
- While the current bar is shorter than the bar at the top of the stack:
- Return the maximum area found.
The virtual zero-height bar is the unsung hero here. It ensures no bar is left behind unprocessed.
Why the Stack Must Be Monotonic
The stack always keeps indices of bars in increasing height order because: - Taller bars can extend through shorter ones. - Shorter bars immediately block all taller bars behind them. - This ordering lets us compute left and right boundaries the moment a bar is popped.
Each bar is pushed once and popped once. No repeats. No chaos.
Every bar enters and leaves the stack exactly one time.
In the worst case, all bars are increasing and sit in the stack together.
Approaches
Brute Force
Expand left and right for every bar. Easy to write, painful to optimize.
Divide and Conquer
Recursively split by the smallest bar. Elegant but slower and harder to implement.
Monotonic StackOptimal
One pass, clean boundaries, interview approved.
Why It Works
When a bar is popped from the stack:
- The current index is its right boundary.
- The new stack top is its left boundary.
- The maximum rectangle for that bar can be computed immediately.
No guessing. No revisiting.
Code Walkthrough
Real implementations in multiple programming languages. Select a language to view idiomatic code.
1def largestRectangleArea(heights: list[int]) -> int:2 """Find largest rectangle area using monotonic stack."""3 stack: list[int] = []4 max_area = 056 for i in range(len(heights) + 1):7 # Use 0 as sentinel for final cleanup8 h = heights[i] if i < len(heights) else 0910 while stack and h < heights[stack[-1]]:11 # Pop and calculate area12 height = heights[stack.pop()]13 width = i if not stack else i - stack[-1] - 114 area = height * width15 max_area = max(max_area, area)1617 stack.append(i)1819 return max_areaReal World Use Cases
- 1Skyline and geometry problems
- 2Maximum rectangle in binary matrices
- 3Memory allocation analysis
- 4Image region detection
- 5Stock performance windows
Key Insights
- Every bar can define a rectangle.
- The first shorter bar on each side limits how far it can stretch.
- Monotonic stacks are perfect for next smaller or next greater element problems.
- The sentinel bar simplifies edge cases and saves you from cleanup logic.
- If you understand this problem, a whole family of stack problems suddenly becomes much easier.
When to Use
Use a monotonic stack when you need to find spans, ranges, or boundaries. It shines when each element depends on its nearest smaller or greater neighbor. You want linear time with predictable behavior.
When NOT to Use
If two pointers or simple iteration solves the problem cleanly, do not force a stack. Stacks are powerful, but unnecessary stacks are how bugs are born.
Common Interview Pitfalls
- Forgetting the sentinel bar at the end.
- Off-by-one errors in width calculation.
- Storing heights instead of indices.
- Not handling the empty stack case.
- Adding a cleanup loop instead of using a sentinel.
Interview Questions & Answers
Why use a stack instead of two arrays for left/right bounds?
The stack computes both bounds on-the-fly in one pass. When we pop, we know both bounds immediately: left is the new stack top, right is the current index.
What does 'monotonic' mean in this context?
The stack maintains elements in strictly increasing height order. Whenever a smaller element arrives, we pop until the invariant is restored.
Why add a zero-height bar at the end?
It acts as a sentinel that's shorter than everything, forcing all remaining stack elements to be popped and processed. Without it, you'd need a separate cleanup loop.
How does this relate to Trapping Rain Water?
Both can use monotonic stacks! In Trapping Rain Water, the stack finds valleys to fill. Here, it finds how far each bar extends. Same tool, different application.
Can this be solved with Two Pointers?
Not directly. Two Pointers works for Trapping Rain Water because we only need running max boundaries. Here, we need to know exact left/right bounds for each bar—stack is the right tool.