How to Solve Largest Rectangle in Histogram on LeetCode
The Largest Rectangle in Histogram is a classic stack problem on LeetCode, ideal for demonstrating your knowledge of monotonic stacks and area calculations.
Problem Statement
Given an array of heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example:
Input: heights = [2,1,5,6,2,3]
Output: 10
Why This Problem Matters for Interviews
This problem:
- Tests use of monotonic stacks for range queries
- Involves geometry, array, and stack skills
- Is a foundation for advanced "area" or interval problems
Stack-Based Approach (Optimal)
Use a stack to store indices of increasing bars. When you find a bar lower than the top, pop and calculate area.
Time Complexity: O(n)
Space Complexity: O(n)
def largestRectangleArea(heights: list[int]) -> int:
stack = []
max_area = 0
heights.append(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_area
Key Interview Talking Points
- The idea behind a monotonic stack for interval calculation
- How widths are computed for each popped bar
- Why a zero is appended to heights
- Handling edge cases: empty histogram, all same height
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack | O(n) | O(n) |
Pro Interview Tips
- Draw the stack operations on a sample input.
- Explain how each pop determines a maximal rectangle.
- Practice with test cases