084. Largest Rectangle in Histogram

At a Glance

• Topic: Array
• Pattern: Analyze Pattern
• Difficulty: Hard
• LeetCode: 084

Problem Statement

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4] Output: 4

Constraints:

1 <= heights.length <= 105
0 <= heights[i] <= 104

Approach & Solution Steps

• 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 JS Solution

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;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.