AlgoMaster Logo

Largest Rectangle in Histogram

hardFrequency9 min readUpdated June 23, 2026

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 figuring out, for each bar, how far left and how far right a rectangle of that bar's height can extend. Answer that efficiently for every bar and the maximum area follows.

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

Consider every possible rectangle. A rectangle in this histogram is defined by a left boundary and a right boundary, with its height equal to the minimum bar height in that range. Its area is min_height * (right - left + 1).

We try all pairs of (left, right), compute the minimum height in that range, calculate the area, and track the maximum. To avoid recomputing the minimum from scratch for each pair, we fix left and extend right one step at a time, updating a running minimum as we go.

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 100,000 bars. The next approach splits the problem recursively to cut the work to O(n log n).

Approach 2: Divide and Conquer

Intuition

Any rectangle in the histogram falls into one of three cases relative to the shortest bar in the range: it uses the shortest bar (so it spans the full range at that bar's height), it lies entirely to the left of the shortest bar, or it lies entirely to the right.

The first case is easy to compute directly: the area is minHeight * (right - left + 1), where minHeight is the shortest bar in the range. For the other two cases, we recurse on the subarray left of the shortest bar and the subarray right of it. The shortest bar caps the height of any rectangle that crosses it, so the largest crossing rectangle is exactly the full-width-times-minimum-height candidate we already counted. That makes splitting at the minimum safe: nothing larger can straddle it.

The answer for a range is the maximum of these three values.

Algorithm

  1. Define a recursive function on the range [left, right].
  2. Base case: if left > right, return 0.
  3. Find the index minIndex of the shortest bar in [left, right].
  4. Compute three candidates:
    • The rectangle using the shortest bar: heights[minIndex] * (right - left + 1).
    • The best rectangle in [left, minIndex - 1] (recurse).
    • The best rectangle in [minIndex + 1, right] (recurse).
  5. Return the maximum of the three.

The cost depends on how the minimum splits each range. When the minimum sits near the middle, the recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). When the histogram is sorted (the minimum is always at one end), each call shrinks the range by one and scans the rest, degrading to O(n^2).

Example Walkthrough

1Range [0,5]: min is index 1 (h=1). Span candidate = 1*6 = 6
0
2
1
1
min
2
5
3
6
4
2
5
3
1*6=6
1/6

Code

This recursion improves on brute force but still degrades to O(n^2) on sorted input, and it rescans each range to find the minimum. A monotonic stack finds every bar's boundaries in one linear pass with no recursion.

Approach 3: Monotonic Stack

Intuition

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]. Given the index of the nearest shorter bar to the left (leftBound) and the nearest shorter bar to the right (rightBound), the rectangle width is rightBound - leftBound - 1, and the area is heights[i] * (rightBound - leftBound - 1).

The problem reduces to finding the nearest smaller bar on both sides of each bar. That is the "next smaller element" problem, which a monotonic stack solves in O(n).

We maintain a stack of bar indices whose heights are in strictly increasing order. Scanning left to right, when we reach a bar shorter than the bar at the stack's top, the stack-top bar's right boundary is the current bar. Its left boundary is the element just below it in the stack, because everything between them was already popped and so was taller. We pop the stack top, compute its area, and repeat until the stack is increasing again.

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 plus cleanup loop) is correct but easy to get wrong, since the cleanup loop duplicates the area logic. The next approach folds both phases into one loop with a sentinel bar.

Approach 4: Monotonic Stack (Sentinel Optimization)

Intuition

The previous approach uses two separate loops: one to process bars left to right, and another to drain whatever remains on the stack. Appending a sentinel bar of height 0 to the end of the array removes the second loop. The zero-height bar is shorter than every real bar (heights are non-negative), so when the scan reaches it, it pops every remaining element off the stack during the main loop. No separate cleanup phase is needed.

This does not change the time or space complexity. It removes the duplicated area logic, so there is only one place to get the width formula right.

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