AlgoMaster Logo

Largest Rectangle in Histogram

Last Updated: March 29, 2026

hard
5 min read

Understanding the Problem

We have a histogram, which is a series of bars sitting side by side, each with width 1 and varying heights. We need to find the largest rectangle that fits entirely within the histogram. This rectangle must be aligned with the bars, meaning its base sits on the x-axis and its sides are vertical.

The rectangle doesn't have to be a single bar. It can span multiple consecutive bars, as long as its height doesn't exceed the shortest bar it covers. So for any group of consecutive bars, the widest rectangle you can form has a height equal to the minimum bar in that group and a width equal to the number of bars.

The core challenge is this: for each bar, how far left and how far right can we extend a rectangle of that bar's height? If we can answer that efficiently for every bar, we can compute the maximum area.

Key Constraints:

  • 1 <= heights.length <= 10^5 -> With up to 100,000 bars, we need O(n log n) or better. An O(n^2) approach checking all pairs will be too slow for the worst case.
  • 0 <= heights[i] <= 10^4 -> Heights can be zero, which means a bar of height 0 acts as a "wall" that blocks any rectangle from extending through it.

Approach 1: Brute Force

Intuition

The most straightforward idea is to consider every possible rectangle. A rectangle in this histogram is defined by choosing a left boundary and a right boundary, then taking the minimum height among all bars in that range. The area is then min_height * (right - left + 1).

So we try all pairs of (left, right), compute the minimum height in that range, calculate the area, and track the maximum.

Algorithm

  1. Initialize maxArea = 0.
  2. For each starting index left from 0 to n-1:
    • Set minHeight = heights[left].
    • For each ending index right from left to n-1:
      • Update minHeight = min(minHeight, heights[right]).
      • Calculate area = minHeight * (right - left + 1).
      • Update maxArea = max(maxArea, area).
  3. Return maxArea.

Example Walkthrough

1Initialize: left=0, right=0, minHeight=2, area=2, maxArea=2
0
left
2
right
1
1
2
5
3
6
4
2
5
3
1/6

Code

This brute force checks every pair of boundaries, which is too slow for large inputs. What if we could find each bar's left and right boundaries in a single pass using a stack?

Approach 2: Monotonic Stack

Intuition

Here's the key observation: for any bar at index i, the largest rectangle that uses heights[i] as its height extends left until it hits a bar shorter than heights[i], and extends right until it hits a bar shorter than heights[i]. If we know the index of the nearest shorter bar to the left (call it leftBound) and the nearest shorter bar to the right (call it rightBound), the width of the rectangle is rightBound - leftBound - 1, and the area is heights[i] * (rightBound - leftBound - 1).

So the problem reduces to: for each bar, find the nearest smaller bar on both sides. This is exactly the "next smaller element" problem, which a monotonic stack solves in O(n).

The idea is to maintain a stack of bar indices where the heights are in strictly increasing order. As we scan left to right, whenever we encounter a bar shorter than the bar at the stack's top, we know we've found the right boundary for the stack-top bar. The left boundary is the element just below it in the stack (because everything between them has already been popped, meaning those bars were all taller). We pop the stack top, compute the area for that bar, and repeat until the stack condition is restored.

Algorithm

  1. Initialize an empty stack and maxArea = 0.
  2. Iterate through each index i from 0 to n-1:
    • While the stack is not empty and heights[i] < heights[stack.top()]:
      • Pop the top index as height = heights[popped].
      • The right boundary is i.
      • The left boundary is the new stack top (or -1 if the stack is empty).
      • Compute width = i - leftBound - 1 and area = height * width.
      • Update maxArea.
    • Push i onto the stack.
  3. After the loop, pop all remaining elements from the stack. For each popped element, the right boundary is n (no shorter bar to the right), and the left boundary is the new stack top (or -1).
  4. Return maxArea.

Example Walkthrough

1i=0: h=2, stack empty, push index 0
0
2
i=0
1
1
2
5
3
6
4
2
5
3
1/8

Code

The two-phase structure (main loop + cleanup loop) works correctly but is a common source of bugs. What if we could guarantee every bar gets processed inside the main loop?

Approach 3: Monotonic Stack (Sentinel Optimization)

Intuition

The previous approach works great, but the code has two separate loops: one for processing bars left to right, and another for draining whatever is left on the stack at the end. We can simplify this by appending a sentinel bar of height 0 at the end of the array. This zero-height bar is shorter than every real bar, so it forces every remaining element off the stack during the main loop. No separate cleanup phase needed.

This doesn't change the time or space complexity, but it makes the code cleaner and less error-prone, which matters in an interview.

Algorithm

  1. Append a 0 to the end of heights.
  2. Initialize an empty stack and maxArea = 0.
  3. Iterate through each index i from 0 to n (inclusive, covering the sentinel):
    • While the stack is not empty and heights[i] < heights[stack.top()]:
      • Pop the top index. The popped bar's height is heights[popped].
      • Width is i if the stack is empty, otherwise i - stack.top() - 1.
      • Update maxArea.
    • Push i.
  4. Return maxArea.

Example Walkthrough

1Append sentinel (h=0) at end. i=0: push 0. i=1: pop 0 (area=2), push 1
0
2
1
1
i=1
2
5
3
6
4
2
5
3
6
0
sentinel
1/6

Code