Largest Rectangle in Histogram
Problem statement
Given an array of non-negative integers heights where each element represents the height of a bar in a histogram (all bars have width 1), find the area of the largest rectangle that can be formed within the histogram.
Your solution must run in $O(n)$ time and $O(n)$ space using a monotonic stack. Additionally:
- Explain how sentinel values simplify the implementation.
- Explain how to handle bars of equal height correctly.
- Show how to return the witness interval $[i, j]$ (the left and right boundaries of the optimal rectangle).
Constraints:
- $1 \le \text{heights.length} \le 10^5$
- $0 \le \text{heights}[i] \le 10^4$
Example 1:
- Input:
heights = [2, 1, 5, 6, 2, 3] - Output:
10 - Explanation: The largest rectangle has area $10$ (spanning bars at indices 2 and 3, with height 5 and width 2).
Example 2:
- Input:
heights = [2, 4] - Output:
4
Show hint
For a rectangle whose height equals one particular bar, what limits how far it can extend to either side?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.