Largest rectangle in a histogram

Hard TimeO(n) SpaceO(n)

Each value in heights is a bar one unit wide, standing side by side as a histogram. Return the area of the largest rectangle that fits entirely inside them. The rectangle has to span consecutive bars, and its height cannot exceed the shortest bar it covers. Heights are zero or greater, and a zero-height bar splits the histogram in two.

Examples

Example 1

Input
heights = [2, 1, 5, 6, 2, 3]
Output
10
The 5 and the 6 together at height 5: 5 × 2 = 10, which beats the 6 × 1 beside it.

Example 2

Input
heights = [2, 2, 2]
Output
6
All three bars at the same height, so the rectangle is the whole histogram: 2 × 3.

The Code

function largestRectangleArea(heights) {
  const stack = [];
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const current = i === heights.length ? 0 : heights[i];
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= current) {
      const top = stack.pop();
      const left = stack.length === 0 ? -1 : stack[stack.length - 1];
      const area = heights[top] * (i - left - 1);
      if (area > best) best = area;
    }
    stack.push(i);
  }
  return best;
}
largestRectangleArea([2, 1, 5, 6, 2, 3]);
Done
Step through largestRectangleArea([2, 1, 5, 6, 2, 3]) call by call

More like this

All stacks & queues examples (8) →