Largest Rectangle in Histogram Hard 0 attempts
LeetCode ↗

Largest Rectangle in Histogram

Hard ArrayTwo Pointers LeetCode

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Sample Input
heights = [2,1,5,6,2,3]
Sample Output
10
Constraints
  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4
Test Cases
Case 1
Args: [[2,1,5,6,2,3]] Expected: 10
Topics
ArrayTwo Pointers

Use a monotonic stack that stores bar indices in increasing height order. When a shorter bar is encountered, pop the stack and compute the area using the popped bar's height as the rectangle height, with width determined by the current index and the new stack top.

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  const n = heights.length;

  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i];
    while (stack.length && heights[stack[stack.length - 1]] > h) {
      const height = heights[stack.pop()];
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }

  return maxArea;
}

Time: O(n) Space: O(n)

Saved in this browser only. Private to you.

JavaScript