Largest Rectangle in Histogram

Examples

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

The largest rectangle uses the bars of height 5 and 6 (indexes 2 and 3): width 2, height min(5, 6) = 5, for an area of 10.

Input: heights = [2, 4]
Output: 4

Using just the bar of height 4 alone gives width 1 * height 4 = 4; using both bars gives width 2 * height 2 = 4. Either way, the best is 4.

Input: heights = [1, 1, 1, 1]
Output: 4

Using all four bars, limited to their shared height of 1, gives width 4 * height 1 = 4, better than using any smaller slice.

Constraints

• 1 <= heights.length <= 10^5

• 0 <= heights[i] <= 10^4

Approach

For any bar, treating it as the shortest bar in some rectangle, that rectangle can stretch left and right until it hits a bar that's shorter. A direct approach checks this by expanding outward from every single bar until it hits something shorter on each side — correct, but slow, since it re-scans a lot of the same ground repeatedly.

A better approach keeps a stack of bar indexes with strictly increasing heights as you scan left to right. Whenever the current bar is shorter than the bar on top of the stack, that means the bar on top has just found its right boundary (the current position), and whatever is now below it on the stack — the next bar down — is its left boundary. Pop it, compute the rectangle it forms, and repeat until the stack's top is shorter than (or equal to) the current bar, then push the current bar's index. Adding one final "zero-height" bar at the very end forces anything left on the stack to be resolved too.

Solutions

Brute Force — Expand Outward From Every Bar

For each bar, treat it as the shortest bar in the rectangle, and expand left and right as far as possible while every bar in that range is at least as tall.

function largestRectangleArea(heights) {
  let best = 0;
  const n = heights.length;

  for (let i = 0; i < n; i++) {
    let left = i;
    while (left > 0 && heights[left - 1] >= heights[i]) left--;

    let right = i;
    while (right < n - 1 && heights[right + 1] >= heights[i]) right++;

    const width = right - left + 1;
    best = Math.max(best, width * heights[i]);
  }

  return best;
}

Time: O(n²) in the worst case (e.g. when all bars are the same height) · Space: O(1)

Optimal — Monotonic Increasing Stack

Scan left to right, keeping a stack of bar indexes with strictly increasing heights. When the current bar is shorter than the bar on top of the stack, that top bar's rectangle is now fully determined — pop it and compute its area, using the current index as the right boundary and the new stack top as the left boundary.

function largestRectangleArea(heights) {
  const stack = []; // indexes with strictly increasing heights, bottom to top
  let best = 0;
  const n = heights.length;

  for (let i = 0; i <= n; i++) {
    const currentHeight = i === n ? 0 : heights[i];

    while (stack.length > 0 && heights[stack[stack.length - 1]] > currentHeight) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      best = Math.max(best, height * width);
    }

    stack.push(i);
  }

  return best;
}

Time: O(n), since each index is pushed and popped at most once · Space: O(n)