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.

class Solution:
    def largestRectangleArea(self, 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 ~10^10 steps — the constraints kill it.

Approach 2 — Divide and conquer on the minimum

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

class Solution:
    def largestRectangleArea(self, 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. Left piece [2] yields 2. Right piece [5, 6, 2, 3] has minimum 2 → candidate 2 × 4 = 8, and its right sub-piece [3] gives 3, while its left sub-piece [5, 6] has minimum 5 → candidate 5 × 2 = 10, whose own sub-piece [6] gives 6. Best overall: 10.

Complexity: O(n log n) when the splits are balanced, but O(n²) 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). O(log n)–O(n) recursion space. Correct, classical, but dominated by the stack solution below.

Approach 3 — Monotonic increasing stack

The insight: a bar’s best rectangle is fenced by its previous smaller and next smaller bars. Both fences fall out of one sweep with a monotonic stack — a stack kept sorted (here: indices of bars with non-decreasing heights) by popping violators. The moment 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 sitting right below it on the stack — so its maximal width, hence area, is known at pop time. A sentinel bar of height 0 appended at the end flushes every remaining bar.

class Solution:
    def largestRectangleArea(self, 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 — don’t “fix” this into a bug.

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.