Largest rectangular area in a histogram

Hard

Problem

heights[i] is the height of a bar of width 1. Return the area of the largest rectangle that fits entirely inside the histogram.

Example 1

Input:  [2, 1, 5, 6, 2, 3]
Output: 10

The bars of height 5 and 6 give a 5 × 2 rectangle.

Also asked as: Largest rectangular Area in Histogram

Test cases

Case 1

Input:    [2,1,5,6,2,3]
Expected: 10

Case 2

Input:    [2,4]
Expected: 4

Case 3

Input:    [6,2,5,4,5,1,6]
Expected: 12

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Monotonic increasing stack of indices

Time O(n)Space O(n)

When a shorter bar appears, pop taller bars; each popped bar’s max rectangle uses it as the height, bounded by the new bar and the stack’s new top.

function largestRectangleArea(h) {
const st = [];
let best = 0;
for (let i = 0; i <= h.length; i++) {
const cur = i === h.length ? 0 : h[i];
while (st.length && h[st[st.length - 1]] >= cur) {
const height = h[st.pop()];
const width = st.length ? i - st[st.length - 1] - 1 : i;
best = Math.max(best, height * width);
}
st.push(i);
}
return best;
}