Largest Rectangle in Histogram

1. Problem & Core Objective

The problem

Given an array heights representing the heights of bars in a histogram, where each bar has width 1, return the area of the largest rectangle that fits entirely within the histogram.

Input:  heights = [2,1,5,6,2,3]      Output: 10

        6 |       █
        5 |     █ █
        4 |     █ █
        3 |     █ █     █
        2 | █   █ █ █   █        ← the 5 and 6 bars give 5 × 2 = 10
        1 | █ █ █ █ █ █
          +-------------
            2 1 5 6 2 3

Constraints:

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

What the interviewer is actually testing

The hardest problem in the section, and one of the harder in the 150.

1. Can you reframe the search? Enumerating all rectangles is O(n²). The unlock is to fix the height — for each bar, find the widest rectangle of exactly that height.
2. Do you see the two-sided span? Each bar extends left and right until it hits something shorter. Both boundaries are "next smaller element" queries — a monotonic stack.
3. Can you handle the start inheritance? When a bar pops a taller one, it inherits that bar's starting position. One line, and without it the algorithm silently under-counts.
4. Do you handle the leftovers? Bars never popped extend to the right edge and need a final drain — or a sentinel to force it.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 10^5.

• O(n²) → 10^10. Too slow.
• O(n log n) → acceptable.
• O(n) → the target.

Step 2 — Reframe the search space

There are O(n²) possible rectangles (every start-end pair), so enumerating them is already too slow. You need a way to consider only O(n) candidates without missing the answer.

The key observation: every maximal rectangle is limited by its shortest bar — that bar's height is the rectangle's height, and the rectangle can't extend past any bar shorter than it.

So instead of enumerating rectangles, enumerate bars:

For each bar i, find the widest rectangle whose height is exactly heights[i].

Every maximal rectangle is captured this way, because its limiting bar will produce it. That's n candidates instead of n².

Step 3 — What defines the width for bar i?

The rectangle of height heights[i] extends left and right until it meets a bar strictly shorter:

left[i]  = index of the nearest bar to the LEFT  that is shorter than heights[i]
right[i] = index of the nearest bar to the RIGHT that is shorter than heights[i]

width = right[i] − left[i] − 1
area  = heights[i] × width

Both are "next smaller element" queries — and that's a monotonic stack (see the section README).

Step 4 — Orientation: increasing stack

Apply the diagnostic question: what event finally lets me determine a bar's span?

A shorter bar arriving. Until one does, the bar can keep extending right. So the pop trigger is "a smaller element arrives", which means the stack holds values in increasing order.

Step 5 — The insight that makes it one pass

You could compute left[] and right[] with two separate stack passes and then combine. That works and is O(n).

But there's a neater formulation. Maintain a stack of (startIndex, height) pairs. When a shorter bar arrives at index i:

• Pop each taller bar and settle it: area = height × (i − startIndex). It can't extend past i.
• Crucially: the arriving bar can extend backwards over everything it just popped — because all of those were taller than it. So it inherits the starting position of the last bar it popped.

That start inheritance is the heart of the algorithm and the line people omit.

Step 6 — Why inheritance is correct

If bar i pops a bar that started at index s, everything from s to i−1 was taller than heights[i]. A rectangle of height heights[i] therefore fits across that whole span — it isn't blocked by anything taller.

So bar i's own rectangle begins at s, not at i.

Without this line, each bar would only measure from its own index rightward, and you'd miss every rectangle that extends leftward through taller bars — silently returning a too-small answer.

Step 7 — The leftovers

Bars still on the stack when the loop ends never met a shorter bar, so they extend all the way to the right edge: width = n − startIndex. Either drain them in a final loop, or append a sentinel bar of height 0 to force every pop inside the main loop.

3. Solution Paths

Approach 1 — Brute force over all pairs

public int largestRectangleArea(int[] heights) {
    int best = 0;
    for (int i = 0; i < heights.length; i++) {
        int minHeight = heights[i];
        for (int j = i; j < heights.length; j++) {
            minHeight = Math.min(minHeight, heights[j]);     // running min across [i, j]
            best = Math.max(best, minHeight * (j - i + 1));
        }
    }
    return best;
}

Every start-end pair, with the limiting height maintained incrementally.

• Time: O(n²).
• Space: O(1).

Counter-questions on this approach

⭐ "You're enumerating rectangles. Is there a smaller set of candidates that still contains the answer?"

Yes — every maximal rectangle is limited by its shortest bar, and that bar's height is the rectangle's height. So instead of O(n²) rectangles I can enumerate n bars, asking for each one "how wide is the rectangle of exactly this height?". Every maximal rectangle is produced by its own limiting bar, so nothing is missed.

"You already maintain minHeight incrementally. Isn't that the optimization?"

It removes a factor of n from a naive O(n³), but the outer double loop is still O(n²). The real saving comes from changing what I enumerate, not from computing each candidate faster.

Approach 2 — For each bar, expand outward

public int largestRectangleArea(int[] heights) {
    int best = 0;
    for (int i = 0; i < heights.length; i++) {
        int left = i, right = i;
        while (left > 0 && heights[left - 1] >= heights[i]) left--;
        while (right < heights.length - 1 && heights[right + 1] >= heights[i]) right++;
        best = Math.max(best, heights[i] * (right - left + 1));
    }
    return best;
}

How it works. This is the right idea — fix the height, find the span — implemented naively by scanning outward.

• Time: O(n²) — a flat histogram makes every scan traverse the whole array.
• Space: O(1).

Counter-questions on this approach

⭐ "This has the right framing but the wrong complexity. What's the redundancy?"

Adjacent bars rescan almost the same region. On [5,5,5,5,5] every bar walks the entire array. The spans are "next smaller element" queries on both sides, and a monotonic stack computes all of them in one pass instead of rediscovering each independently.

"Why >= rather than > in the expansion conditions?"

So that equal-height bars extend through each other. On [5,5,5] each bar should see width 3. With strict > each bar would stop at its neighbour and report width 1, giving 5 instead of 15. Equal heights don't block a rectangle.

Approach 3 — Two passes for left and right boundaries

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] left = new int[n], right = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {                       // nearest shorter bar to the LEFT
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
        left[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }

    stack.clear();
    for (int i = n - 1; i >= 0; i--) {                  // nearest shorter bar to the RIGHT
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
        right[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }

    int best = 0;
    for (int i = 0; i < n; i++) {
        best = Math.max(best, heights[i] * (right[i] - left[i] - 1));
    }
    return best;
}

Trace on [2,1,5,6,2,3]:

Answer: 10 ✓

• Time: O(n) — three linear passes.
• Space: O(n) — two boundary arrays plus the stack.

Counter-questions on this approach

⭐ "Three passes and two extra arrays. Can it be done in one pass?"

Yes — the one-pass version settles each bar at the moment it's popped, which is exactly when its right boundary becomes known. The left boundary comes from the element beneath it on the stack, or from the start it inherited. So both boundaries are available at pop time and the arrays become unnecessary.

"Why >= rather than > in the pop conditions?"

With >=, equal-height bars pop each other, so left[i] may point at a bar of equal height rather than a strictly shorter one. That's still correct for the maximum: the taller-or-equal run is handled by whichever of its bars is processed last, which sees the full span. Using > would also work but the reasoning about which bar reports the full width changes. Either is defensible provided you can say why.

"The sentinel values −1 and n — what are they for?"

They represent "no shorter bar exists on this side", so the rectangle extends to the array edge. Using −1 on the left makes right − left − 1 compute the correct full width with no special case, which is exactly why those particular values are chosen.

Approach 4 — One pass with (start, height) pairs (optimal)

public int largestRectangleArea(int[] heights) {
    Deque<int[]> stack = new ArrayDeque<>();      // {startIndex, height}, heights INCREASING
    int best = 0;

    for (int i = 0; i < heights.length; i++) {
        int start = i;
        while (!stack.isEmpty() && stack.peek()[1] > heights[i]) {
            int[] top = stack.pop();
            best = Math.max(best, top[1] * (i - top[0]));    // settle: height × width
            start = top[0];        // *** INHERIT: this bar can extend back to there ***
        }
        stack.push(new int[]{start, heights[i]});
    }

    // Bars never popped extend to the right edge
    for (int[] rem : stack) {
        best = Math.max(best, rem[1] * (heights.length - rem[0]));
    }
    return best;
}

Full trace on [2,1,5,6,2,3]:

Final drain: {0,1} → 1×(6−0) = 6; {2,2} → 2×(6−2) = 8; {5,3} → 3×(6−5) = 3.

Answer: 10 ✓

Look at i = 4. The arriving bar of height 2 popped bars starting at indices 3 and 2, so it inherits start = 2. It's then pushed as {2, 2}, and in the final drain that gives 2 × (6 − 2) = 8 — a rectangle spanning indices 2 through 5. Without the inheritance it would have been pushed as {4, 2}, giving only 2 × 2 = 4, and the answer for that shape would be wrong.

• Time: O(n) — each bar pushed once, popped at most once.
• Space: O(n).

Counter-questions on this approach

⭐ "Explain the start = top[0] line. What breaks without it?"

When bar i pops a taller bar that began at index s, everything from s to i−1 was taller than heights[i]. So a rectangle of height heights[i] fits across that entire span — it isn't blocked by anything taller. Bar i's own rectangle therefore begins at s, not at i.

Without the line, each bar only measures from its own index rightward, and every rectangle that extends leftward through taller bars is missed.

The cleanest counterexample is [4, 2, 3], where the answer is 6 — the bar of height 2 spans all three positions. Without inheritance it's pushed as {1, 2} instead of {0, 2}, so its width is measured as 2 rather than 3, and the algorithm returns 4. Verified.

It fails silently — no exception, just a smaller answer. And on many inputs it happens to be right anyway (on [2,1,5,6,2,3] it still returns 10, because the winning rectangle comes from a pop that wasn't affected), which makes it exactly the kind of bug that survives casual testing.

⭐ "Prove this is O(n). There's a while inside a for."

Each bar is pushed exactly once — one push per iteration of the outer loop. Each can be popped at most once, and once popped it never returns. So the total number of pops across the entire run is bounded by n, and the inner while consumes from that fixed budget rather than multiplying the outer loop. n pushes + at most n pops = O(n).

"Why does the final drain loop exist? Can you avoid it?"

Bars still on the stack never met a shorter bar, so they extend to the right edge — width n − start. A strictly increasing histogram like [1,2,3] pops nothing during the main loop, so all the answers come from that drain.

You can avoid it by appending a sentinel bar of height 0 (or −1), which is shorter than everything and forces every remaining bar to pop inside the main loop. That trades the extra loop for an array copy. Both are fine; the sentinel is tidier when heights can be 0, in which case use −1.

"You use > in the pop condition. What about equal heights?"

With >, equal-height bars are not popped — so a new bar of the same height is pushed with its own start, and the earlier one stays. The maximum is still correct, because the earlier equal bar retains the wider span and will report it during the drain or a later pop.

Using >= would also give the right maximum, popping equal bars and letting the new one inherit their start. Both work; what matters is being able to say why.

"Why int[] pairs rather than just indices?"

Because the inherited start is not any bar's own index — it's a position the bar acquired by popping others. An index-only stack can't express that, which is why the alternative formulation (below) uses the element beneath the popped one as the left boundary instead.

Approach 5 — One pass with indices only

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();     // indices; heights increasing
    int best = 0, n = heights.length;

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];         // sentinel forces the final drain

        while (!stack.isEmpty() && heights[stack.peek()] > h) {
            int height = heights[stack.pop()];
            int leftBoundary = stack.isEmpty() ? -1 : stack.peek();
            int width = i - leftBoundary - 1;
            best = Math.max(best, height * width);
        }
        stack.push(i);
    }
    return best;
}

How it works. Instead of carrying an inherited start, the left boundary is read from the element beneath the popped one — because the stack is increasing, that's the nearest shorter bar to the left. The i == n sentinel of height 0 forces everything to drain.

• Time: O(n).
• Space: O(n).

Counter-questions on this approach

⭐ "Where did the start inheritance go?"

It's implicit. Because the stack is increasing, the element directly beneath the popped one is its nearest shorter bar on the left — so stack.peek() after the pop gives the left boundary directly. The inheritance in Approach 4 was a way of carrying that same information forward explicitly. Two encodings of one idea.

"Why stack.isEmpty() ? -1 : stack.peek()?"

If the stack empties, the popped bar was shorter than everything before it, so its rectangle extends to the left edge. Using −1 makes i − (−1) − 1 = i give the correct full width with no special case — the same sentinel reasoning as in Approach 3.

"Is the i <= n loop bound a typo?"

No, it's deliberate. The extra iteration at i == n uses a virtual bar of height 0, which is shorter than every real bar and therefore pops all of them. That replaces the separate drain loop. Using heights[i] there would throw, which is why the ternary guards it.

Comparison

4. Why the Optimal Wins

Against enumerating rectangles. There are O(n²) rectangles but only n maximal ones worth considering — each limited by its own shortest bar. Changing what you enumerate, rather than computing each candidate faster, is what removes the quadratic factor.

Against expanding outward. Same framing, but adjacent bars rescan overlapping regions — [5,5,5,5,5] makes every bar traverse the whole array. The stack computes every span in a single pass by keeping unresolved bars around until their right boundary appears.

One pass vs two. Both O(n). The two-pass version is easier to verify and I'd write it if unsure. The one-pass version settles each bar at pop time, when both boundaries are simultaneously known — the right boundary is the arriving bar, the left is the inherited start (or the element beneath). Fewer moving parts, harder to derive.

Why O(n) is the floor. Every bar must be examined, since the answer could be limited by any of them. So O(n) is optimal.

The transferable idea:

When an answer is bounded by the minimum over a range, enumerate by "which element is the minimum" rather than by range — and use a monotonic stack to find each element's span in O(1) amortized.

That same move solves Maximal Rectangle (run this once per row over a running histogram of column heights), Sum of Subarray Minimums, and Trapping Rain Water's stack formulation.

5. Java Prerequisites

ArrayDeque holding pairs

Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{start, height});
stack.peek()[0];      // start
stack.peek()[1];      // height

Generic over int[], which is an object. Fine as a stack element since nothing compares them — unlike as a map key, where identity equality would break things. See 05.

Iterating a Deque without draining it

for (int[] rem : stack) { ... }        // iterates top → bottom, leaves the stack intact

ArrayDeque's iterator goes front to back — top of stack first. Order doesn't matter here since we take a maximum over all remaining bars.

(Note: java.util.Stack iterates bottom to top, the opposite. Another reason to prefer ArrayDeque — consistent semantics.)

The sentinel trick

for (int i = 0; i <= n; i++) {
    int h = (i == n) ? 0 : heights[i];

The extra iteration uses a virtual bar shorter than everything, forcing a full drain. Use −1 rather than 0 if heights can be 0, since a real 0-height bar wouldn't pop other 0-height bars with a strict >.

Overflow analysis

heights[i] * width

Maximum height 10^4, maximum width 10^5, so the largest area is 10^9 — which fits in int (max ≈ 2.1 × 10^9), but not by a wide margin. Worth computing the bound aloud: if either limit were larger, I'd accumulate in long.

Guard before peeking

while (!stack.isEmpty() && stack.peek()[1] > heights[i])

&& short-circuits, so peek() is never dereferenced on an empty deque. Reversing the operands would throw NullPointerException.

6. Interview Communication Guide

Clarifying questions

1. "Does every bar have width exactly 1?" — yes, which is what makes the area height × count of bars.
2. "Can heights be zero?" — yes, per the constraints, which affects the choice of sentinel value.
3. "Do I return the area, or the rectangle's boundaries?" — the area; boundaries would just mean recording indices when best improves.
4. "Can the histogram be empty?" — constraints say n >= 1.
5. "Could the area overflow an int?" — max is about 10^9, so it fits, but I'd check rather than assume.

The pitch

"There are O(n²) possible rectangles, so enumerating them is already too slow. The reframe is to notice that every maximal rectangle is limited by its shortest bar — that bar's height is the rectangle's height.

So instead of enumerating rectangles, I enumerate bars: for each bar, what's the widest rectangle of exactly that height? Every maximal rectangle gets produced by its own limiting bar, so nothing is missed, and that's n candidates instead of n².

The width for bar i runs left and right until it meets a strictly shorter bar. Both of those are 'next smaller element' queries — which is a monotonic stack. Since a shorter bar is what resolves a span, the stack holds increasing heights.

I'll keep (startIndex, height) pairs. When a shorter bar arrives, I pop each taller bar and settle it — its width is from its start up to here. The important detail: the arriving bar inherits the start of the last bar it popped, because everything it just popped was taller, so a rectangle of its height fits back across that whole span. Without that line the algorithm silently under-counts.

Bars left on the stack at the end never met a shorter bar, so they extend to the right edge — a final drain handles them, or I can append a sentinel of height 0 to force it.

O(n): each bar is pushed once and popped at most once, so the inner loop consumes a budget of n rather than multiplying the outer one."

Edge cases to raise proactively

The strictly increasing case is the one to volunteer — nothing is popped during the main loop, so if you forget the drain (or the sentinel) you return 0 or a wrong small value. It's the case that proves the leftover handling is load-bearing.

[5,5,5,5] is the second: equal-height bars must form one wide rectangle (20, not 5), which checks the pop comparison handles ties correctly.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "Maximal Rectangle — largest rectangle of 1s in a binary matrix." (LC 85)

Run this algorithm once per row, over a running histogram of column heights: height[c] += 1 if the cell is 1, else reset to 0. Each row's histogram gives the best rectangle whose bottom edge is that row, and the overall answer is the maximum across rows. O(rows × cols) total. This is the classic escalation and the reason this problem matters.

"Return the rectangle's coordinates, not just the area."

Record (left, right, height) whenever best improves — all three are available at the moment a bar is settled. No complexity change.

"What if heights could be updated between queries?"

The stack is a one-pass construction and can't handle updates. You'd need a segment tree storing the minimum per range and recursing on the minimum's position — O(n log n) to build and O(log n) per update, with queries costing O(n) in the worst case. Worth stating plainly that the monotonic stack doesn't apply once the array is mutable.

"What if bars had different widths?"

The algorithm survives with one change: width becomes the sum of the widths of the spanned bars rather than a count of indices. Keep a prefix-sum array of widths and compute spans from it. Still O(n).

"What if the histogram streamed in and you couldn't store it?"

The stack already holds only unresolved bars, so memory is O(unresolved) rather than O(n) — small on mostly-increasing data, but still O(n) on a decreasing stream. You'd need to store heights alongside indices rather than dereferencing the array. The answer is only final once the stream ends, since a late short bar can settle many earlier ones.

"Largest square rather than rectangle?"

Different problem — it's a DP, where dp[i][j] is the side of the largest square ending at that cell, computed as 1 + min(up, left, diagonal). O(mn). The monotonic stack doesn't transfer, because the square constraint couples width and height. See 19 — Dynamic Programming.

"Sum of the minimums over all subarrays." (LC 907)

Same machinery, different accumulation: for each element, use the monotonic stack to find how many subarrays it is the minimum of — (i − left) × (right − i) — and add value × count. O(n). A good demonstration that "find each element's span" is the reusable primitive here, not the area formula.