Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Largest Rectangle in Histogram

Find the largest rectangle that fits under a histogram in O(n), using a monotonic stack to find how far each bar can stretch left and right.

Updated Medium read: 8 min read

Approaches at a glance

ApproachTimeSpace
Brute force over every rangeO(n²)O(1)
Monotonic stackO(n)O(n)

The problem

You are given the heights of the bars of a histogram. Every bar is one unit wide and they stand side by side with no gaps. Return the area of the largest rectangle that fits entirely inside the bars.

[2, 1, 5, 6, 2, 3]   →  10
[2, 4]               →  4
[2, 2, 2]            →  6

The first example, with the answer marked X:

         #
      X  X
      X  X
      X  X     #
#     X  X  #  #
#  #  X  X  #  #
2  1  5  6  2  3

The rectangle covers the bars of height 5 and 6. It is 2 wide and can only be 5 tall, because it must fit under the shorter of the two: 2 × 5 = 10.

Approach 1: brute force

A rectangle covers a run of neighbouring bars, and its height is limited by the shortest bar in the run. Try every run, tracking the shortest bar as the run grows.

JavaScript

function largestRectangleAreaBruteForce(heights) {
  let best = 0;
  for (let start = 0; start < heights.length; start++) {
    let lowest = Infinity;
    for (let end = start; end < heights.length; end++) {
      lowest = Math.min(lowest, heights[end]);
      best = Math.max(best, lowest * (end - start + 1));
    }
  }
  return best;
}

Python

def largest_rectangle_area_brute_force(heights):
    best = 0
    for start in range(len(heights)):
        lowest = float("inf")
        for end in range(start, len(heights)):
            lowest = min(lowest, heights[end])
            best = max(best, lowest * (end - start + 1))
    return best

Time O(n²): every pair of start and end. Space O(1).

A better question to ask

Instead of trying every run, think about each bar in turn and ask: what is the biggest rectangle whose height is exactly this bar's height?

Such a rectangle starts at the bar and spreads left and right for as long as the neighbouring bars are at least as tall. It stops, on each side, at the first bar that is shorter. So for each bar:

width = (position of the first shorter bar on the right)
      − (position of the first shorter bar on the left) − 1
area  = height × width

The best rectangle overall must be one of these, because every rectangle is exactly as tall as the shortest bar it covers. The problem is now "for each bar, find the nearest shorter bar on each side", which is the next-smaller-element question that a monotonic stack answers in one pass.

Approach 2: monotonic stack

Walk through the bars keeping a stack of the bars whose rectangles are still open: they have not yet met a shorter bar on their right, so they could still stretch further. The heights on the stack increase from bottom to top.

When a new bar arrives that is shorter than the bar on top, the top bar's rectangle has just been closed off on the right. Pop it and work out its area:

  • Right edge: the new bar's position. That is the first shorter bar on the right.
  • Left edge: the bar now on top of the stack. Because the stack is in increasing order, the bar beneath is the nearest one to the left that is shorter. If the stack is empty, nothing to the left is shorter and the rectangle reaches all the way to the start.

Keep popping while the top is at least as tall as the new bar, then push the new bar.

At the end, some bars are still open. Processing one extra, imaginary bar of height 0 after the last real one closes them all, with no separate clean-up loop.

JavaScript

function largestRectangleArea(heights) {
  const open = []; // indexes of bars still able to stretch right; heights increasing
  let best = 0;
 
  for (let i = 0; i <= heights.length; i++) {
    // One imaginary bar of height 0 at the end closes every open rectangle.
    const current = i < heights.length ? heights[i] : 0;
 
    while (open.length > 0 && heights[open[open.length - 1]] >= current) {
      const height = heights[open.pop()];
      const leftEdge = open.length > 0 ? open[open.length - 1] + 1 : 0;
      best = Math.max(best, height * (i - leftEdge));
    }
    open.push(i);
  }
  return best;
}

Python

def largest_rectangle_area(heights):
    # Indexes of bars still able to stretch right; heights increasing.
    open_bars = []
    best = 0
 
    for i in range(len(heights) + 1):
        # One imaginary bar of height 0 at the end closes every open rectangle.
        current = heights[i] if i < len(heights) else 0
 
        while open_bars and heights[open_bars[-1]] >= current:
            height = heights[open_bars.pop()]
            left_edge = open_bars[-1] + 1 if open_bars else 0
            best = max(best, height * (i - left_edge))
        open_bars.append(i)
    return best

leftEdge is the first position the rectangle covers and i is the first position it does not, so i − leftEdge is its width.

Walkthrough

[2, 1, 5, 6, 2, 3]. The stack is shown as positions, with heights in brackets.

i (height) Popped Left edge Width Area Stack after best
0 (2) 0 (2) 0
1 (1) 0 (2) 0, stack empty 1 − 0 = 1 2 1 (1) 2
2 (5) 1 (1), 2 (5) 2
3 (6) 1 (1), 2 (5), 3 (6) 2
4 (2) 3 (6) 3 4 − 3 = 1 6 6
2 (5) 2 4 − 2 = 2 10 1 (1), 4 (2) 10
5 (3) 1 (1), 4 (2), 5 (3) 10
6 (end, 0) 5 (3) 5 6 − 5 = 1 3 10
4 (2) 2 6 − 2 = 4 8 10
1 (1) 0, stack empty 6 − 0 = 6 6 6 10

The answer is 10, found when the bar of height 5 was popped: it is hemmed in by the height-1 bar on its left and the height-2 bar on its right, leaving a width of 2.

Notice the bar of height 2 at position 4. Its rectangle has a left edge of 2, not 4: it stretches back across the two taller bars that were popped before it. The stack remembers that those positions are available even though the bars themselves are gone.

Time O(n): each bar is pushed once and popped once. Space O(n) for the stack, reached when the heights only rise.

What happens with equal heights

The loop pops while the top is at least as tall as the new bar, so a bar of equal height closes the one before it. That gives the earlier bar a width that is too small, which looks like a bug.

It is not, because the later equal bar inherits the space. For [2, 2, 2]:

  • Position 1 pops position 0 with a width of 1 (area 2): an underestimate.
  • Position 2 pops position 1 with a width of 2 (area 4): still an underestimate.
  • The final imaginary bar pops position 2. The stack is empty, so the left edge is 0 and the width is 3: area 6, the right answer.

The last bar in any run of equal heights always sees the full width, and only the maximum matters.

  • Daily Temperatures is the simpler version: next greater element, and only on one side.
  • Trapping Rain Water also works bar by bar, but asks about the tallest bars on each side instead of the nearest shorter ones.
  • The largest rectangle of 1s in a grid (LeetCode 85) is solved by treating each row as the base of a histogram and running this function once per row.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(largestRectangleArea([2, 1, 5, 6, 2, 3])); // 10
console.log(largestRectangleArea([2, 2, 2])); // 6

Python

print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))  # 10
print(largest_rectangle_area([2, 2, 2]))  # 6

The comment after each line is the result you should see.

Common mistakes

  • Leaving bars on the stack at the end. Without the imaginary final bar or a clean-up loop, a histogram that only rises, such as [1, 2, 3], returns 0.
  • Using the popped bar's own position as the left edge. The rectangle may stretch left across bars that were popped earlier. The left edge comes from the bar now on top of the stack.
  • Forgetting the empty-stack case. When nothing is left on the stack, the rectangle starts at position 0, not at the popped bar.
  • Storing heights instead of positions. Widths are differences between positions, so positions must be on the stack.
  • Measuring the width as i − leftEdge + 1. Position i is the shorter bar that closed the rectangle. It is not part of it.

Original problem: LeetCode 84: Largest Rectangle in Histogram