Largest Rectangle in Histogram

Given an array of bar heights (each bar has width 1), return the area of the largest rectangle that can be formed in the histogram.

Why this is worth learning

Popping a height means its first strictly lower bar on the right has arrived. The stack reveals how far that height can extend left without crossing a lower barrier.

Before coding: one-minute experiment

For heights [2,2,2], what area must eventually be considered even though equal heights are not popped immediately?

Function signature

func LargestRectangleArea(heights []int) int

Inputs / outputs

• heights: non-negative integers.
• Return: maximum rectangle area.

Example

heights = [2,1,5,6,2,3]
Output: 10

Rectangle of height 5 across bars 5 and 6.

Constraints

• 0 <= len(heights) <= 100_000
• 0 <= heights[i] <= 1_000_000_000

Core idea (near-solution)

Use a monotonic increasing stack of indices. When a bar breaks the increasing order, it becomes the right boundary for bars taller than it.

Invariant: indices increase, and their heights are non-decreasing. Equal-height bars can coexist until a strictly lower height closes them.

Algorithm (step-by-step)

1. After the last real bar, process a virtual height-0 bar at index len(heights). It flushes pending positive heights without appending into the caller's backing array.
2. Iterate through indices:
   • While the current height is less than the height at stack top:
     • Pop the top; treat it as the height of a rectangle.
     • The right boundary is the current index.
     • The left boundary is the new stack top (or -1 if empty).
     • Compute area and update best.
   • Push the current index.
3. Return the best area.

Correctness sketch

The stack contains indices with non-decreasing heights. When a lower current height arrives, a popped bar cannot extend through this right boundary. After the pop, the remaining top supplies a left boundary for the rectangle considered, giving width right-left-1, or right when the stack is empty. Every bar between those boundaries is at least the popped height. Equal-height bars can remain stacked; later popping their earliest representative exposes the full plateau width, so no maximal rectangle is lost. Any optimal rectangle has some minimum-height bar and is considered when its right boundary closes. A virtual zero-height sentinel closes all positive-height candidates at the end.

Trace (hand walkthrough)

Example input:
heights = [2,1,5,6,2,3]
Output: 10

Rectangle of height 5 across bars 5 and 6.

Walk:
- i=0: push index 0 (height 2)
- i=1, height 1: pop index 0, area=2*1=2; then push index 1
- i=2 and i=3: push indices 2,3; stack indices [1,2,3] have heights [1,5,6]
- i=4 height=2: pop 6 -> area 6*1=6; pop 5 -> area 5*2=10 (best)
- finish scan with sentinel 0 to flush stack; best=10

Pitfalls to avoid

• Forgetting the sentinel (misses rectangles ending at the end).
• Using decreasing stack instead of increasing.

Debugging lens

Test increasing input so the sentinel must do the work, decreasing input, zeros, and equal plateaus. Width is i-left-1, not i-left. The reference uses a virtual sentinel and does not append to the caller's slice.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• Process a virtual sentinel height 0 at index len(heights) to flush the stack without mutating the input.
• Use indices to compute widths: i - stack[top] - 1.

Contract precision

The input is not mutated. The sentinel is a virtual final index with height zero. Areas under the published bounds require a 64-bit int target.

Reconstruction checkpoint

For heights [2,2,2], what area must eventually be considered even though equal heights are not popped immediately?

Return to Stack + Monotonic · Module quiz