084. Largest Rectangle in Histogram

At a Glance

• Topic: stack
• Pattern: Monotonic Stack / Queue
• Difficulty: Hard
• Companies: Amazon, Google, Microsoft, Meta, Bloomberg
• Frequency: Very High
• LeetCode: 84

Problem (one-liner)

Given an array heights of bar heights in a histogram (width 1 per index), return the area of the largest axis-aligned rectangle.

Recognition Cues

• Histogram / bars / rectangle area
• Need index of previous smaller and next smaller → monotonic increasing stack
• Same skeleton as “maximal rectangle in binary matrix” row-wise

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — every (left, right) interval as candidate height min(heights[left:right+1]) — O(n³) time.
• Better — for each bar as minimum height, expand until shorter neighbors — O(n²) time / O(1) extra.
• Acceptable — precompute previous smaller and next smaller per index with two stack passes — same O(n) as optimal but more moving parts.
• Optimal — single scan with monotonic increasing index stack and sentinel height 0 at virtual index n — O(n) time / O(n) space; prefer this for one clean loop.

Optimal Solution

Go

func largestRectangleArea(heights []int) int {
	stackIndices := []int{}
	maxArea := 0
	for index := 0; index <= len(heights); index++ {
		var currentHeight int
		if index == len(heights) {
			currentHeight = 0
		} else {
			currentHeight = heights[index]
		}
		for len(stackIndices) > 0 && currentHeight < heights[stackIndices[len(stackIndices)-1]] {
			topIndex := stackIndices[len(stackIndices)-1]
			stackIndices = stackIndices[:len(stackIndices)-1]
			var leftBoundary int
			if len(stackIndices) == 0 {
				leftBoundary = -1
			} else {
				leftBoundary = stackIndices[len(stackIndices)-1]
			}
			width := index - leftBoundary - 1
			area := heights[topIndex] * width
			if area > maxArea {
				maxArea = area
			}
		}
		if index < len(heights) {
			stackIndices = append(stackIndices, index)
		}
	}
	return maxArea
}

JavaScript

function largestRectangleArea(heights) {
	const stackIndices = [];
	let maxArea = 0;
	for (let index = 0; index <= heights.length; index++) {
		const currentHeight = index === heights.length ? 0 : heights[index];
		while (
			stackIndices.length > 0 &&
			currentHeight < heights[stackIndices[stackIndices.length - 1]]
		) {
			const topIndex = stackIndices.pop();
			const leftBoundary =
				stackIndices.length === 0
					? -1
					: stackIndices[stackIndices.length - 1];
			const width = index - leftBoundary - 1;
			const area = heights[topIndex] * width;
			if (area > maxArea) {
				maxArea = area;
			}
		}
		if (index < heights.length) {
			stackIndices.push(index);
		}
	}
	return maxArea;
}

Walkthrough

heights = [2,1,5,6,2,3]

Popping 5 at index when we see 1 (or sentinel 0) gives width spanning to previous smaller.

Invariant: stack is strictly increasing in heights[index]; when we pop topIndex, the new top is previous smaller to the left, and index is first smaller to the right.

Edge Cases

• All zeros
• Single bar
• Strictly increasing heights
• All same height — one big rectangle
• Last bar needs sentinel height 0 to flush stack (hence index == len loop)

Pitfalls

• Width formula right - left - 1 after pop
• Forgetting sentinel at end — last tall bar never popped

Similar Problems

• 739. Daily Temperatures — monotonic stack “next greater” (Medium warm-up).
• 42. Trapping Rain Water — histogram geometry; two-pointer “rain” Hard sibling.
• 239. Sliding Window Maximum — monotonic deque; fixed-window max (Hard sibling).

Variants

• Maximal rectangle in a binary matrix — compress each row into histogram heights; reuse this routine per row (O(rows × cols) with sparse optimizations possible).
• Largest rectangle with constraint (e.g., width cap, banned indices) — often needs DP or segment tree; monotonic stack alone may not apply.
• Online heights stream — need full history or windowed variant; classic offline stack breaks without replay buffer.

Mind-Map Tags

#monotonic-stack #histogram #largest-rectangle #sentinel-pop #width-from-boundaries #cartesian-tree