Largest Rectangle in Histogram

Problem

You are given an array heights where heights[i] is the height of the i-th bar of a histogram; every bar has width 1 and stands on a common baseline. Return the area of the largest axis-aligned rectangle that fits entirely inside the histogram.

Equivalently: choose a contiguous range of bars [l, r]; the rectangle over that range has area (r - l + 1) * min(heights[l..r]). Maximize that product.

Examples

Example 1

Input: heights = [2, 1, 5, 6, 2, 3] Output: 10 Explanation: bars 5 and 6 (indices 2–3) support a rectangle of height 5 and width 2 → area 10.

Example 2

Input: heights = [2, 4] Output: 4 Explanation: best is the single bar of height 4 (area 4); using both bars gives only 2 × 2 = 4 as well.

Example 3

Input: heights = [3, 3, 3] Output: 9 Explanation: the whole histogram is a 3 × 3 rectangle.

Constraints

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4
• With n = 10^5, the O(n²) all-pairs scan is too slow — an O(n) or O(n log n) solution is expected.

Think about it first

TL;DR

Monotonic increasing stack of indices with a sentinel bar of height 0 — O(n) time, O(n) space.

Approach 1 — Brute force (expand around each bar)

Every optimal rectangle is limited by its shortest bar. So for each bar i, treat it as the shortest: expand left and right while neighbors are at least as tall, and take height * width.

def largestRectangleArea(heights: list[int]) -> int:
    n = len(heights)
    best = 0
    for i in range(n):
        h = heights[i]
        left = i
        while left > 0 and heights[left - 1] >= h:
            left -= 1
        right = i
        while right < n - 1 and heights[right + 1] >= h:
            right += 1
        best = max(best, h * (right - left + 1))
    return best

Complexity: O(n²) time (a flat histogram makes every bar expand across the whole array), O(1) space. At n = 10^5 that is about 10^10 steps, which exceeds the time limit.

Approach 2 — Divide and conquer on the minimum

The shortest bar m of any range either spans the entire range (area heights[m] × range width) or is excluded. Excluding it splits the range into the parts left and right of m. Recurse on both sides and take the best of the three candidates. This is divide and conquer: split at a pivot, solve the subproblems independently, combine.

def largestRectangleArea(heights: list[int]) -> int:
    def solve(lo: int, hi: int) -> int:  # inclusive bounds
        if lo > hi:
            return 0
        m = lo
        for j in range(lo + 1, hi + 1):
            if heights[j] < heights[m]:
                m = j
        full = heights[m] * (hi - lo + 1)
        return max(full, solve(lo, m - 1), solve(m + 1, hi))

    return solve(0, len(heights) - 1)

Walkthrough of Example 1 — [2, 1, 5, 6, 2, 3]: the global minimum is 1 at index 1, giving the full-width candidate 1 × 6 = 6. The left piece [2] yields 2. The right piece [5, 6, 2, 3] has minimum 2, so its full-width candidate is 2 × 4 = 8; its right sub-piece [3] gives 3, and its left sub-piece [5, 6] has minimum 5, giving 5 × 2 = 10, whose own sub-piece [6] gives 6. Best overall: 10.

flowchart TD
    A["[2,1,5,6,2,3]<br/>min 1, full 6"] --> B["[2]<br/>area 2"]
    A --> C["[5,6,2,3]<br/>min 2, full 8"]
    C --> D["[5,6]<br/>min 5, full 10"]
    C --> E["[3]<br/>area 3"]
    D --> F["empty, 0"]
    D --> G["[6]<br/>area 6"]

Complexity: O(n log n) when the splits are balanced, but O(n²) in the worst case (sorted heights split off one bar at a time); a segment tree for the range-minimum makes it a guaranteed O(n log n). Recursion space is O(log n) to O(n). Correct and classical, but slower than the stack solution below.

Approach 3 — Monotonic increasing stack

A bar’s best rectangle is fenced by its previous smaller and next smaller bars. Both fences fall out of a single sweep with a monotonic stack: a stack of indices whose heights stay non-decreasing bottom to top, maintained by popping any bar taller than the current one. When the current bar i is shorter than the stack’s top, the popped bar has just met its next-smaller element (i), and its previous-smaller element is the index now below it on the stack, so its maximal width and area are known at pop time. A sentinel bar of height 0 appended at the end flushes every remaining bar.

def largestRectangleArea(heights: list[int]) -> int:
    ext = heights + [0]  # sentinel flushes the stack at the end
    stack: list[int] = []  # indices; ext heights non-decreasing bottom→top
    best = 0
    for i, h in enumerate(ext):
        while stack and ext[stack[-1]] > h:
            height = ext[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, height * width)
        stack.append(i)
    return best

Walkthrough of Example 1 — ext = [2, 1, 5, 6, 2, 3, 0]:

Answer: 10 — the height-5 rectangle over indices 2–3.

(A common two-pass variant precomputes previous smaller index and next smaller index arrays with the same stack trick, then takes one max pass — identical O(n) idea, just materialized.)

Complexity: O(n) time — every index is pushed once and popped at most once. O(n) space for the stack (worst case: strictly increasing heights).

Common pitfalls

• Computing the popped bar’s width as i - popped_index instead of i - stack_top_after_pop - 1 — the bar may extend left past its own index over previously popped equal-or-taller bars.
• Forgetting to flush the stack after the sweep; the sentinel 0 bar handles it, otherwise you need an explicit drain loop with i = n.
• Off-by-one at an empty stack: the left fence is index -1, making the width i - (-1) - 1 = i, not i - 1.
• Equal heights: with a strict > pop condition, earlier equal bars get undersized widths, but the last bar of an equal run computes the full run’s width, so the maximum is still correct. Leave the strict comparison in place.

Pattern takeaway

“For every element, find the nearest smaller (or greater) element on each side” is the monotonic-stack signature: sweep once, keep the stack sorted, and resolve each element at the moment it gets popped, when both of its boundaries are simultaneously visible. Any problem that reduces to previous/next-smaller — maximal rectangles, trapping water variants, subarray-minimum sums — yields to this same O(n) sweep.