Largest Rectangle in Histogram

Problem

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.

Examples

The brute-force approach

For every pair (i, j), the rectangle spanning bars i through j has height = min(heights[i..j]) and width = j - i + 1. Try all pairs and track the maximum.

max_area = 0

for i in range(len(heights)):
    min_h = heights[i]
    for j in range(i, len(heights)):
        min_h = min(min_h, heights[j])      # ← find bottleneck height
        area = min_h * (j - i + 1)
        max_area = max(max_area, area)

return max_area

O(n²), all pairs. For 10,000 bars, that's 50 million iterations. The stack approach finds the answer in O(n) by processing each bar exactly twice (once when pushed, once when popped).

Spotting the pattern

This is a Stack problem. The key question to ask yourself:

For each bar, how do I find the farthest left and right it can extend without being cut short by a shorter bar?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.