Largest Rectangle in Histogram Hard 0 attempts
LeetCode ↗

Largest Rectangle in Histogram

Hard ArrayTwo Pointers LeetCode

Picture a histogram made of bars of width 1 standing side by side, with heights giving each bar's height. Find the biggest rectangle you can fit within the outline of these bars and return its area.

Input Format
Implement largestRectangleArea(heights). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
heights = [2,2]
Output
4
Constraints
  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4
Test Cases (2)
Case 1
Args: [[2,1,5,6,2,3]] Expected: 10
Case 2
Args: [[2,2]] Expected: 4
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.

javascript
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