Largest Rectangle In Histogram

HARD✓ CHIP-TIMEDLC #84 — FULL STATEMENT ↗

The drill: Bars of given heights stand side by side with unit width. Find the area of the largest axis-aligned rectangle that fits entirely under the skyline they form.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of bar heights arrives, each bar standing on the same baseline with a width of exactly one unit, side by side with no gaps.

Together the bars form a skyline, and the drill is to find the single largest rectangle — any width, any height — that fits entirely underneath that skyline without poking above any bar it spans.

A candidate rectangle's height is limited by the shortest bar it stretches across, so the answer trades width for height across every possible contiguous stretch of bars. The result is that one largest area.

EX 01

heights = [3]

→ 3

MINIMUM SIZE, SINGLE BAR

EX 02

heights = [4, 4]

→ 8

EQUAL HEIGHTS SPAN TOGETHER

EX 03

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

→ 9

INCREASING — BEST IS THE LAST THREE BARS

histogram can hold up to around a hundred thousand bars
bar heights are non-negative and can repeat or hit zero
each bar contributes a width of exactly one unit
answer is the single largest rectangle area under the skyline

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Trying every pair of bars as left and right edges works, but recomputing the limiting height for each pair from scratch is wasteful. What if, for every bar, you asked how far IT alone could stretch as the rectangle's height?

HINT 2 THE STRUCTURE

A bar can stay the shortest bar in its rectangle all the way until it hits a shorter neighbor on either side. Finding the nearest shorter bar to the left and to the right, for every bar, is the whole problem.

HINT 3 ONE STEP FROM THE ANSWER

Sweep left to right with a stack of indices at increasing height. When the next bar is shorter than the stack's top, pop: the popped bar's rectangle is bounded on the left by the new top (or the wall) and on the right by the current index.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SKYLINE STACKPATTERN · MONOTONIC STACKheights = [6, 2, 5, 4, 5, 1, 6]

THE STACK — INDEX → HEIGHT

— empty —

STEP 1

Heights are 6, 2, 5, 4, 5, 1, 6. Keep a stack of bar indices at increasing height — a shorter bar closes rectangles.

STEP 1 / 12 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/largest-rectangle-in-histogram.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []  # indices, strictly increasing heights
        best = 0
        n = len(heights)
        for i in range(n + 1):
            h = heights[i] if i < n else 0  # sentinel flushes whatever remains
            while stack and heights[stack[-1]] >= h:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                best = max(best, height * width)
            stack.append(i)
        return best

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 13 LN

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        best = 0
        for i in range(n):
            min_h = heights[i]
            for j in range(i, n):              # anchor i, expand right...
                min_h = min(min_h, heights[j])  # ...tracking the running minimum
                best = max(best, min_h * (j - i + 1))
        return best

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>(); // indices, strictly increasing heights
        int best = 0;
        for (int i = 0; i <= n; i++) {
            int h = (i < n) ? heights[i] : 0; // sentinel flushes whatever remains
            while (!stack.isEmpty() && heights[stack.peek()] >= h) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                best = Math.max(best, height * width);
            }
            stack.push(i);
        }
        return best;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 17 LN

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int best = 0;
        for (int i = 0; i < n; i++) {
            int minH = heights[i];
            for (int j = i; j < n; j++) {
                minH = Math.min(minH, heights[j]);
                best = Math.max(best, minH * (j - i + 1));
            }
        }
        return best;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED