Largest Rectangle in Histogram
Find the area of the largest rectangle in the histogram.
Problem Understanding
heights lists the bars of a histogram from left to right, each bar one unit wide. Return the area of the biggest rectangle that fits entirely inside the bars.
Example:
- Input:
[2, 1, 5, 6, 2, 3] - Output:
10(The rectangle from index 2 to 3 with height 5 has area 5 * 2 = 10).
Algorithm Strategy
We use a Monotonic Increasing Stack.
Core Idea:
For each bar h at index i, if we know the first bar to the left that is smaller (left_limit) and the first bar to the right that is smaller (right_limit), then the maximum width for a rectangle with height h is right_limit - left_limit - 1.
One-Pass Logic:
- Maintain a stack of indices with increasing heights.
- When we encounter a bar
h[i]smaller thanh[stack.top()], it meansh[i]is the Right Limit forh[stack.top()]. - Pop
top. Now the New Top of the stack is the Left Limit for the popped bar. - Calc Area:
height * (i - stack.top() - 1). - Repeat until stack rule is satisfied, then push
i.
Interactive Visualization
Visualize how we pop bars when a shorter one appears, calculating potential areas.
Dry Run
Input: [2, 1, 5, 6, 2, 3]. The stack starts as [-1]; at i = 6 = n the height read is 0.
| i | h | Pops (height × width = area) | Stack after | Best |
|---|---|---|---|---|
| - | - | - | [-1] |
0 |
| 0 | 2 | - | [-1, 0] |
0 |
| 1 | 1 | bar 0: 2 × 1 = 2 | [-1, 1] |
2 |
| 2 | 5 | - | [-1, 1, 2] |
2 |
| 3 | 6 | - | [-1, 1, 2, 3] |
2 |
| 4 | 2 | bar 3: 6 × 1 = 6; bar 2: 5 × 2 = 10 | [-1, 1, 4] |
10 |
| 5 | 3 | - | [-1, 1, 4, 5] |
10 |
| 6 | 0 | bar 5: 3 × 1 = 3; bar 4: 2 × 4 = 8; bar 1: 1 × 6 = 6 | [-1, 6] |
10 |
Result: 10 — bars 2 and 3, height 5.
Edge Cases & Common Mistakes
- Increasing Seq:
[1, 2, 3]. Nothing is popped while the bars are read; the extra step ati = nreads height 0 and pops them all, so no second loop is needed. - Single Bar: Area = height.
- Left Limit: If stack empty after pop, left limit is conceptually
-1.
Solution
Monotonic Stack O(N).
Largest Rectangle in Histogram Code
1var largestRectangleArea = function(heights) {2 const stack = [-1];3 let best = 0;4 const n = heights.length;5 for (let i = 0; i <= n; i++) {6 const h = i === n ? 0 : heights[i];7 while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= h) {8 const height = heights[stack.pop()];9 const width = i - stack[stack.length - 1] - 1;10 best = Math.max(best, height * width);11 }12 stack.push(i);13 }14 return best;15};