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.

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 in the stack have increasing heights.

Algorithm (step-by-step)

1. Append a sentinel bar of height 0 to flush the stack at the end.
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

• Invariant: indices in the stack have increasing heights.
• The stack remains monotonic, so each element’s next boundary is discovered when it is popped.
• Each index is pushed and popped at most once, and its answer is finalized then.
• Therefore all outputs computed on pop are correct.

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..3 push heights [2,1,5,6] (stack indices)
- 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.

Complexity

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

Implementation notes (Go)

• Append a sentinel height 0 to flush the stack.
• Use indices to compute widths: i - stack[top] - 1.