Skip to main content

25. Largest Rectangle in Histogram

hardAsked at Indeed

Find the largest rectangular area in a histogram — Indeed's infrastructure team uses monotonic-stack reasoning for memory-region packing in their large-scale index builder.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4

Examples

Example 1

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

Example 2

Input
heights = [2,4]
Output
4

Approaches

1. Brute force — all pairs

For each pair (i, j) compute the min height in the range and the resulting area.

Time
O(n^2)
Space
O(1)
function largestRectangleArea(heights) {
  let max = 0;
  for (let i = 0; i < heights.length; i++) {
    let minH = heights[i];
    for (let j = i; j < heights.length; j++) {
      minH = Math.min(minH, heights[j]);
      max = Math.max(max, minH * (j - i + 1));
    }
  }
  return max;
}

Tradeoff:

2. Monotonic increasing stack

Maintain a stack of bar indices in increasing height order; when a shorter bar is encountered, pop and compute the rectangle width using the current index as the right boundary.

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

Tradeoff:

Indeed-specific tips

Indeed infrastructure interviewers use this problem to verify that candidates can reason about the sentinel (appending 0) that forces all remaining bars to be popped cleanly — explain it before coding.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Largest Rectangle in Histogram and other Indeed interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →