Largest Rectangle in Histogram

Ishaan S Published 24 Oct, 2026

A histogram is drawn as a row of vertical bars that stand side by side on a common baseline. Every bar is exactly 1 unit wide, and the height of bar i is heights[i].

Find the largest area of an axis-aligned rectangle that fits completely inside the histogram. The rectangle must sit on the baseline and may span several neighbouring bars, but its height can never exceed the shortest bar it covers.

Return that maximum area (it is 0 if every bar has height 0).

Example 1

Input: heights = [3,1,4,4,2] Output: 8 Why: The two bars of height 4 next to each other give a 4 × 2 rectangle of area 8. Spanning all five bars only allows height 1 (area 5).

Example 2

Input: heights = [5] Output: 5 Why: With a single bar the best rectangle is the bar itself.

Example 3

Input: heights = [4,2,0,3,2,5] Output: 6 Why: The bar of height 0 cuts the histogram in two. On the right, height 2 across the three bars 3, 2, 5 gives area 6, which beats every other choice.

Constraints

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

Pattern Path · Stacks · problem 50 of 169

Any rectangle in the histogram is limited by the shortest bar it covers. Try fixing that shortest bar instead of fixing the two ends.

If bar i is the shortest bar of the rectangle, the rectangle stretches left and right until it hits a strictly shorter bar. So you need, for every bar, its nearest shorter neighbour on each side.

Keep a stack of indices whose heights increase from bottom to top. When a bar arrives that is not taller than the top, it is the right boundary of the top bar, and the index just below it on the stack is the left boundary. Pop, compute the area, repeat.

Target: O(n) time, O(n) extra space.

Start simple

For every starting bar, extend to the right while tracking the minimum height seen so far and score height × width: O(n²) time, O(1) space.

The key idea

Think about the optimal rectangle: its height equals the height of some bar i inside it, and it extends as far as possible in both directions, stopping just before the first strictly shorter bar on each side. So the answer is the maximum over all bars of heights[i] × (right − left − 1), where left and right are the nearest shorter bars.

A monotonic stack finds both boundaries in one pass. Keep indices on the stack with heights increasing upwards. When bar i is not taller than the top of the stack, the top bar has found its right boundary (i), and the element just beneath it is its left boundary, because everything between them was popped earlier for being taller. Pop it, record its area, and keep popping while the condition holds. Then push i.

Appending a sentinel bar of height 0 forces every remaining bar off the stack at the end, so no special clean-up loop is needed. Each index is pushed and popped exactly once, giving linear time.

Equal heights are handled safely: popping an equal bar early may under-count its width, but the last bar of that equal run sees the true left boundary and records the full area.

Complexity

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

Python

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        bars = heights + [0]  # a zero-height sentinel empties the stack at the end
        stack = []            # indices of bars, heights increasing from bottom to top
        best = 0
        for i, h in enumerate(bars):
            # Bar i is the right boundary for every taller bar still on the stack.
            while stack and bars[stack[-1]] >= h:
                height = bars[stack.pop()]
                left = stack[-1] if stack else -1  # nearest shorter bar on the left
                best = max(best, height * (i - left - 1))
            stack.append(i)
        return best

JavaScript

var largestRectangleArea = function(heights) {
  const bars = [...heights, 0]; // a zero-height sentinel empties the stack at the end
  const stack = [];             // indices of bars, heights increasing from bottom to top
  let best = 0;
  for (let i = 0; i < bars.length; i++) {
    // Bar i is the right boundary for every taller bar still on the stack.
    while (stack.length && bars[stack[stack.length - 1]] >= bars[i]) {
      const height = bars[stack.pop()];
      const left = stack.length ? stack[stack.length - 1] : -1; // nearest shorter bar on the left
      best = Math.max(best, height * (i - left - 1));
    }
    stack.push(i);
  }
  return best;
};

What the interviewer is checking

The interviewer wants to see you reframe the search (fix the limiting bar, not the endpoints) and then recognise the "nearest smaller element" structure that a monotonic stack solves in one pass.

Mistakes to avoid

Forgetting to flush the stack at the end, which misses rectangles that reach the last bar (a sentinel 0 fixes this).
Using the popped index itself as the left edge instead of the index now on top of the stack, which ignores taller bars popped earlier and shrinks the width.
When the stack is empty after a pop, the popped bar was the shortest so far, so its rectangle reaches back to index 0 and its width is i, not i - popped.
Divide-and-conquer on the minimum bar degrades to O(n²) on sorted input.

Follow-ups to expect

Find the largest all-ones rectangle in a binary matrix. (Run this per row on column heights.)
Can you compute both boundary arrays separately? (Two passes of nearest smaller element.)
What if bars have different widths? (Track cumulative x positions instead of indices.)

In real software

Finding the largest free rectangle in a skyline or occupancy profile shows up in layout engines, warehouse slotting and image processing (largest empty region in a mask).

Practice next

Topics #050 #t-stacks Array Hard Monotonic Stack Practice Stack