Largest Rectangle in Histogram
Asked at Microsoft
Problem
Given an array of integers representing bar heights in a histogram where all bars have the same width, find the area of the largest rectangular bar that fits entirely within the histogram.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | HARD | View all Microsoft questions → |
How to Think About It
Brute force: For every pair of bars, calculate the rectangle area using the minimum height in that range. O(n^3) with naive min finding.
Optimized brute force: For each bar, expand left and right to find the tallest bars that allow this bar as the minimum. O(n^2).
Monotonic stack: Maintain a stack of increasing heights. When a shorter bar is encountered, pop and compute area for each popped bar.
The popped bar extends from the previous stack top to the current index, giving left and right boundaries.
Single pass with monotonic stack achieves O(n) time and O(n) space.
Optimal Approach
Use a monotonic increasing stack of indices. Iterate through the bars with a sentinel 0 appended at the end. For each bar, while the stack top has a height greater than the current bar, pop it and calculate the area using the popped bar as the minimum height. The width extends from the new stack top to the current index. Track the maximum area across all such calculations.
What Trips People Up in Real Interviews
Confirm bar widths are uniform (typically 1 unit).
Explain the key insight: each bar is the minimum height for some range of consecutive bars.
Walk through the stack invariant: stack stores indices with strictly increasing heights.
Handle the final cleanup: pop remaining stack elements using n as the right boundary.
State time as O(n) because each element is pushed and popped at most once.
Solution Code
def largestRectangleArea(heights):
stack = []
max_area = 0
heights.append(0)
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
heights.pop()
return max_areaFrequently Asked Questions
What is the Largest Rectangle in Histogram problem?
Given an array of integers representing bar heights in a histogram where all bars have the same width, find the area of the largest rectangular bar that fits entirely within the histogram.
How do you solve Largest Rectangle in Histogram?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Largest Rectangle in Histogram?
Largest Rectangle in Histogram is asked at Microsoft. It is a hard difficulty problem.
What are common mistakes on Largest Rectangle in Histogram?
- Confirm bar widths are uniform (typically 1 unit).
- Explain the key insight: each bar is the minimum height for some range of consecutive bars.
- Walk through the stack invariant: stack stores indices with strictly increasing heights.
- Handle the final cleanup: pop remaining stack elements using n as the right boundary.
- State time as O(n) because each element is pushed and popped at most once.