Largest Rectangle in Histogram Solution

Problem

You are given an array of bar heights representing a histogram where each bar has width 1. Find the area of the largest rectangle that can be formed using consecutive bars — the rectangle's height is capped by the shortest bar it spans.

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The rectangle spanning bars at indices 2 and 3 (heights 5 and 6) has height 5 and width 2, giving area 10.

A useful counter-example: heights = [3, 1, 3] produces area 3, not 9 — the center bar of height 1 prevents the two outer bars from forming a single wide rectangle.

Intuition

A rectangle's height is always limited by its shortest bar, so expanding a rectangle rightward helps only as long as we do not encounter something shorter. Instead of checking every possible pair of left and right edges (O(n²)), we can process each bar exactly once by maintaining a stack of bars that are still "open" candidates — bars whose widest possible rectangle has not yet been determined because nothing shorter has blocked them on the right. The instant a shorter bar appears, every taller bar in the stack has found its right boundary.

Approach 1 — Brute Force

For every possible left edge, scan rightward while tracking the minimum height seen. The current rectangle's height is that running minimum; update the max area at each step.

Loop over every starting index left.
Initialize min_height to heights[left].
Loop right from left to n-1.
Update min_height = min(min_height, heights[right]).
Update max_area = max(max_area, min_height * (right - left + 1)).
Return max_area.

1class Solution:
2    def largestRectangleArea(self, heights: list[int]) -> int:
3        max_area = 0
4        for left in range(len(heights)):
5            min_height = heights[left]  # tallest the rectangle can be starting here
6            for right in range(left, len(heights)):
7                min_height = min(min_height, heights[right])  # shrinks as we hit shorter bars
8                max_area = max(max_area, min_height * (right - left + 1))
9        return max_area

Time: O(n²) — every pair of (left, right) indices is examined once.
Space: O(1) — only a few scalar variables; no extra data structures.

Approach 2 — Monotonic Stack

Maintain a stack of bar indices in strictly increasing order of height. When a bar shorter than the stack top arrives, every taller bar in the stack has found its right boundary — pop and compute area. A sentinel height-0 bar appended to the end forces all remaining bars to be processed.

Append a virtual sentinel bar of height 0 to the end of heights; store as extended.
Maintain a stack of indices; push index 0.
For each index i, while extended[stack[-1]] > extended[i], pop p:
- bar_height = extended[p]
- width = i if stack is empty, else i - stack[-1] - 1
- Update max_area.
Push i.
Return max_area.

1class Solution:
2    def largestRectangleArea(self, heights: list[int]) -> int:
3        extended = heights + [0]  # sentinel forces all remaining candidates off the stack
4        stack: list[int] = []    # indices; heights at these indices are strictly increasing
5        max_area = 0
6
7        for i, current_height in enumerate(extended):
8            while stack and extended[stack[-1]] > current_height:
9                bar_height = extended[stack.pop()]
10                # left boundary is the new stack top (exclusive); right boundary is i (exclusive)
11                width = i if not stack else i - stack[-1] - 1
12                max_area = max(max_area, bar_height * width)
13            stack.append(i)
14
15        return max_area

Time: O(n) — each bar is pushed and popped at most once, so the total work across all iterations is O(n).
Space: O(n) — the stack holds at most n indices in the worst case (a strictly increasing histogram).

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Tiny inputs or when code clarity outweighs performance
Monotonic Stack	O(n)	O(n)	Any real workload; this is the expected interview answer

Common Mistakes

Miscomputing the width when the stack is non-empty — after popping index p, the left boundary is stack[-1] (the new top), not p - 1. The popped bar may have been preceded by taller bars that were already popped earlier, leaving a gap. The formula i - stack[-1] - 1 accounts for this gap correctly.
Forgetting the sentinel — without a height-0 element at the end, bars that are never "beaten" by a shorter bar stay on the stack and are silently ignored. Always process the extra sentinel or loop to n with a virtual height of 0.
Confusing stack.top() with the popped bar's left neighbor — after popping p, the new stack top is the exclusive left wall, not p's own left neighbor in the array.
Accessing heights[stack[-1]] when the stack might hold the sentinel index — if you push the sentinel index n onto the stack and then try to access heights[n] in a later while-loop condition, you will read out of bounds. Guard with i < n when accessing the original array or use the extended copy throughout.
Using the Java remove(Object) overload instead of remove(int) — list.remove(heights[p]) removes the first element equal to heights[p], not the last element; always call list.remove(list.size() - 1) to pop by index.

Largest Rectangle in Histogram — Solution