35. Largest Rectangle in Histogram
A histogram is drawn with bars of width 1 standing side by side; bar i has height heights[i].
Return the area of the largest rectangle that fits entirely inside the histogram. The rectangle must be axis-aligned and can span several adjacent bars, but it cannot rise above the shortest bar it covers.
Input: heights = [3,1,4,4,2] Output: 8
Explanation: The two bars of height 4 form a 4 × 2 rectangle. Spanning the last three bars only gives 2 × 3 = 6.
Input: heights = [5] Output: 5
Input: heights = [2,2,2,2] Output: 8
Constraints
1 <= heights.length <= 10^50 <= heights[i] <= 10^4
💡 Hint 1
Every optimal rectangle is as tall as some bar i. For that bar, how far can the rectangle stretch left and right?
💡 Hint 2
It stretches until the first strictly shorter bar on each side. Finding those boundaries naively is O(n²).
💡 Hint 3
Keep a stack of indices with increasing heights. When a shorter bar arrives, it is the right boundary of every taller bar you pop, and the new stack top is the left boundary.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
The best rectangle is limited by its shortest bar, so for each bar i consider the widest rectangle of height heights[i]: it extends until the nearest strictly shorter bar on each side. A monotonic stack of indices with increasing heights finds both boundaries in one pass. Scan left to right, and treat position n as an extra bar of height 0 so everything gets flushed at the end. While the current height is below the height at the stack top, pop that index top: the current index i is its right boundary, and the index now on top of the stack (or -1 if empty) is its left boundary, giving area heights[top] * (i - left - 1). Then push i. Each index is pushed and popped once.
function largestRectangleArea(heights) {
const n = heights.length;
const stack = [];
let best = 0;
for (let i = 0; i <= n; i++) {
const h = i === n ? 0 : heights[i];
while (stack.length && h < heights[stack[stack.length - 1]]) {
const top = stack.pop();
const left = stack.length ? stack[stack.length - 1] : -1;
best = Math.max(best, heights[top] * (i - left - 1));
}
stack.push(i);
}
return best;
}class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length, best = 0, top = -1;
int[] stack = new int[n + 1];
for (int i = 0; i <= n; i++) {
int h = i == n ? 0 : heights[i];
while (top >= 0 && h < heights[stack[top]]) {
int height = heights[stack[top--]];
int left = top >= 0 ? stack[top] : -1;
best = Math.max(best, height * (i - left - 1));
}
stack[++top] = i;
}
return best;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} heights
* @return {number}
*/
function largestRectangleArea(heights) {
}Run your code to see results here.