Largest Rectangle in Histogram

HardStackArrayStackMonotonic Stack

Problem

Given the heights of adjacent, equal-width bars forming a histogram, find the area of the largest rectangle that fits entirely within the histogram's outline, using one or more consecutive bars as its base.

Example. For heights [2, 1, 5, 6, 2, 3], the largest rectangle has area 10, formed by the two bars of height 5 and 6 standing together (width 2, height 5).

Key idea

Checking every pair of left and right boundaries and finding the shortest bar between them works but is far too slow. The key observation is that the largest rectangle limited by a given bar's height extends exactly as far left and right as the bars stay at least that tall, so what matters for each bar is the nearest shorter bar on each side.

Find those boundaries efficiently with a single pass and a stack that stays increasing in height from bottom to top. Scan bars left to right, pushing each index while the stack keeps increasing. When a shorter bar appears, the bar at the top has just found its right boundary: the current position. Pop it; its left boundary is whatever index is now exposed at the top, or the very start if the stack is empty. Compute that bar's area from those boundaries and its height, then repeat against the new top before moving on. Track the largest area seen throughout.

Solution

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    // Sentinel height of 0 past the end flushes any bars still left on the stack.
    const currentHeight = i === heights.length ? 0 : heights[i];

    // Current bar is shorter than the top: the top bar's right boundary is now known.
    while (stack.length > 0 && heights[stack[stack.length - 1]] > currentHeight) {
      const height = heights[stack.pop()!];
      const leftBoundary = stack.length === 0 ? -1 : stack[stack.length - 1]; // Nearest shorter bar to the left.
      const width = i - leftBoundary - 1;
      maxArea = Math.max(maxArea, height * width);
    }

    stack.push(i);
  }

  return maxArea;
}

Complexity

  • Time: O(n). Each bar's index is pushed and popped from the stack exactly once.
  • Space: O(n). The stack holds up to every index in the worst case, such as strictly increasing heights.

Watch out for

  • Flush the stack after the scan, or use a trailing zero-height sentinel, so bars still on it get resolved.
  • The left boundary after a pop is the new top's index, not the popped index, and both boundaries are excluded from the width.

Pattern

This extends the monotonic stack technique for finding the nearest smaller element on both sides, used for distance in daily temperatures, to compute an area instead.

Related questions