Skip to main content

24. Largest Rectangle in Histogram

hardAsked at Autodesk

Find the largest rectangle area that can fit under a histogram skyline.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers heights representing the histogram's bar heights where the width of each bar is 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. Expand from each bar

For each bar walk left and right to find how far the bar's height extends.

Time
O(n^2)
Space
O(1)
for i: left=i, right=i; while left-1>=0 and h[left-1]>=h[i] left--; similarly right; area=h[i]*(right-left+1); update best.

Tradeoff:

2. Monotonic stack

Maintain a stack of indices with increasing heights. On a smaller bar, pop and compute area for the popped bar using current index and new stack top.

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

Tradeoff:

Autodesk-specific tips

Largest-rectangle reasoning underlies Autodesk's footprint optimization in space planning (Revit/AutoCAD layout tools).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Autodesk coding interview questions

See all Autodesk problems →

Companies that also ask Largest Rectangle in Histogram