Skip to content

Largest Rectangle in Histogram

The Problem

You're given an array of non-negative integers representing the heights of histogram bars. Each bar has width 1. Find the area of the largest rectangle that fits entirely under the bars.

This is LeetCode 84, and it shows up constantly in interviews. More importantly, it's the foundation for an entire family of problems. Solve this one in O(N), and a lot of harder problems become straightforward.

The Key Observation

Here's the idea. Pick any bar — say bar i with height heights[i]. What's the widest rectangle you can draw using heights[i] as the height?

You can extend left as long as every bar is at least as tall as heights[i]. You can extend right under the same condition. The moment you hit a shorter bar, you stop.

Sound familiar? That "how far can I extend" is exactly the range of dominance from the previous lesson. The left boundary L[i] is where the first shorter bar sits on the left. The right boundary R[i] is where the first shorter bar sits on the right.

So the widest rectangle with height heights[i] has:

  • Height = heights[i]
  • Width = R[i] - L[i] - 1
  • Area = heights[i] * (R[i] - L[i] - 1)

The answer is the maximum area across all bars. That's it. The entire problem reduces to: compute boundaries, compute areas, take the max.

Walkthrough: [2, 1, 5, 6, 2, 3]

Let's draw the histogram:

6       |
5     | |
4     | |
3     | |   |
2 |   | | | |
1 | |   | | |
  0 1 2 3 4 5

Now compute boundaries (nearest strictly smaller element):

i heights[i] L[i] R[i] Width Area
0 2 -1 1 1 2
1 1 -1 6 6 6
2 5 1 4 2 10
3 6 2 4 1 6
4 2 1 6 4 8
5 3 4 6 1 3

The maximum area is 10, from bar 2 (height 5, width 2, covering bars 2 and 3).

Let's double-check that. Bars 2 and 3 have heights 5 and 6. A rectangle of height 5 fits under both of them. Area = 5 * 2 = 10. Yep.

Notice how bar 1 (height 1) dominates the entire array — its rectangle is 1 * 6 = 6. Wide but short. Bar 4 (height 2) dominates indices 2-5, giving 2 * 4 = 8. The winner is bar 2 with its taller but narrower rectangle.

Trace of largest rectangle computation showing width, height, and area for each bar

The Two-Pass Solution

This is the cleanest version to understand. Three separate loops:

Pass 1 — Left boundaries. Scan left to right with a monotonic stack. For each bar, pop everything taller or equal, then the stack top is the left boundary.

Pass 2 — Right boundaries. Scan right to left with a fresh stack. Same logic.

Pass 3 — Compute areas. Loop through all bars, compute heights[i] * (R[i] - L[i] - 1), track the max.

Total time: O(N). Three passes, each O(N). Space: O(N) for the boundary arrays and the stack.

This is the version I'd recommend writing first. It's easy to debug, easy to reason about, and maps directly to the boundary concept you already know.

The Single-Pass Trick

There's a slicker approach that computes everything in one left-to-right scan. It's worth understanding because you'll see it in editorial solutions, and it saves a constant factor.

The idea: maintain a stack of indices. Scan from left to right. When the current bar is shorter than the stack top, it means the stack top's right boundary has been found — it's the current index. Pop the stack top and compute its area right then and there.

Here's the logic step by step:

  1. For i from 0 to N (yes, go one past the end — we'll explain why):
  2. Let cur_height = heights[i] if i < N, else 0.
  3. While the stack isn't empty and heights[stack.top()] >= cur_height:
    • Pop the top. Call its height h.
    • The right boundary is i (the current index that triggered the pop).
    • The left boundary is the new stack top (or -1 if the stack is empty).
    • Width = i - left - 1. Area = h * width. Update the max.
  4. Push i.

Why go to index N with height 0? Because a bar of height 0 is shorter than everything, so it forces all remaining bars off the stack. Without this, bars that are never popped (because nothing shorter appears to their right) would be missed.

Let's trace through [2, 1, 5, 6, 2, 3]:

  • i=0: Stack empty. Push 0. Stack: [0]
  • i=1: heights[0]=2 >= 1. Pop 0: h=2, left=-1, width=1-(-1)-1=1, area=2. Push 1. Stack: [1]
  • i=2: heights[1]=1 < 5. Push 2. Stack: [1, 2]
  • i=3: heights[2]=5 < 6. Push 3. Stack: [1, 2, 3]
  • i=4: heights[3]=6 >= 2. Pop 3: h=6, left=2, width=4-2-1=1, area=6. Then heights[2]=5 >= 2. Pop 2: h=5, left=1, width=4-1-1=2, area=10. Then heights[1]=1 < 2. Push 4. Stack: [1, 4]
  • i=5: heights[4]=2 < 3. Push 5. Stack: [1, 4, 5]
  • i=6 (sentinel): cur_height=0. Pop 5: h=3, left=4, width=6-4-1=1, area=3. Pop 4: h=2, left=1, width=6-1-1=4, area=8. Pop 1: h=1, left=-1, width=6-(-1)-1=6, area=6.

Max area across all pops: 10. Same answer, one pass.

When to Use Which Version

The two-pass version is better when:

  • You need the boundary arrays for something else (contribution technique, for example)
  • You want code that's easy to explain in an interview
  • You're extending the solution (like the 2D matrix version coming in lesson 4)

The single-pass version is better when:

  • You want minimal code
  • You don't need the boundary arrays — you just need the final answer
  • You're optimizing for speed in competitive programming

Both are O(N) time and O(N) space. The difference is purely stylistic.

Why This Problem Matters

Largest Rectangle in Histogram isn't just an interview classic. It's a gateway problem. Once you can solve it in O(N):

  • 2D Maximal Rectangle becomes solvable by reducing each row to a 1D histogram (lesson 4 of this chapter).
  • Sum of Subarray Minimums uses the exact same boundary computation but for counting instead of area (lesson 3).
  • Trapping Rain Water is another boundary-based histogram problem that uses similar thinking.

The pattern is always the same: compute boundaries with the monotonic stack, then use those boundaries for whatever the problem actually asks. The rectangle is just the most visual, most intuitive application of that pattern.

Common Mistakes

Off-by-one in width calculation. The width is R[i] - L[i] - 1, not R[i] - L[i]. Remember, L[i] and R[i] are the boundary indices — they're outside the rectangle, not inside it.

Forgetting the sentinel in single-pass. If you scan from 0 to N-1 only, bars that never get popped (because they're followed by taller bars all the way to the end) will be left on the stack and their areas won't be computed. Always include the sentinel pass at i = N with height 0.

Integer overflow. Heights and widths can both be up to 10^5, so the product can reach 10^10. Use long long.