Free lesson · DSA Mastery - Interview Prep, End to End

Largest Rectangle in Histogram

Medium8 min readdsastacks

Largest Rectangle in Histogram

Largest Rectangle in Histogram is the monotonic-stack capstone of the entire module - and one of the most celebrated problems in all of algorithms. Given bar heights, find the area of the largest rectangle that fits entirely under the histogram. The brute force is O(n²); the monotonic stack solves it in a single O(n) sweep using a stack of indices, computing for each bar the largest rectangle in which that bar is the shortest. Every idea from this section converges here: indices for distances, the pop-resolves-on-a-smaller-arrival rule, sentinel handling, and span computation between previous-smaller and next-smaller bars.

The insight: a rectangle is defined by its height (the shortest bar it spans) and its width (how far that shortest bar can extend left and right before hitting a shorter bar). So for each bar as the limiting height, the width runs from just after the previous smaller bar to just before the next smaller bar. A single increasing monotonic stack discovers both boundaries: when a bar is popped (because a shorter bar arrived), the arriving bar is its next-smaller boundary and the new stack top is its previous-smaller boundary.

The Problem

Given an array of integers heights representing the histogram's bar heights where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

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

Explanation: The largest rectangle has area 10 (bars of height 5 and 6 span width 2: 5 x 2 = 10).

Example 2:

Input:  heights = [2,4]
Output: 4

Constraints:

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

Approaches Overview

Brute force takes each bar as the limiting height and expands left/right while bars stay at least that tall. The monotonic stack finds, for every bar, its previous-smaller and next-smaller boundaries in one pass, computing each candidate rectangle's area as it pops.

Approach 1: Brute Force

The Idea

For each bar i as the rectangle's height, expand left and right while neighboring bars are >= heights[i], measuring the width, and track height × width. O(n²) - each bar may expand across the whole array.

Logic Flowchart

graph TD
    A["maxArea = 0"] --> B["for each bar i"]
    B --> C["expand left while heights[left-1] >= heights[i]"]
    C --> D["expand right while heights[right+1] >= heights[i]"]
    D --> E["area = heights[i] * (right - left + 1)"]
    E --> F["maxArea = max(maxArea, area)"]
    F --> G{"more bars?"}
    G -->|Yes| B
    G -->|No| H["Return maxArea"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the brute force. Each bar is taken as the rectangle height; we expand left and right while neighbors are at least as tall, then compute area as height times width. Expansion can be linear per bar, giving quadratic time.

Code

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

This Java code takes each bar as the height, expands left and right while neighbors are at least as tall, and computes the rectangle area. It runs in quadratic time.

Complexity

Time: O(n²). Space: O(1). The stack does it in O(n).

Approach 2: Monotonic Increasing Stack of Indices - Optimal (The Capstone)

The Idea

Maintain a stack of indices whose heights are increasing from bottom to top. Iterate i over the bars (plus one extra sentinel index at the end with height 0 to flush the stack):

• While the stack is non-empty and the current height h is less than the height at the top index, the top bar's rectangle is now bounded on the right - pop it. Its height is heights[popped]; its width spans from just after the new stack top (its previous-smaller boundary) to just before i (its next-smaller boundary). If the stack becomes empty, the bar extends all the way left, so width is i. Compute area = height × width and update the max.
• Push i.

The trailing sentinel of height 0 forces every remaining bar to be popped and measured. Each bar is pushed and popped once → O(n).

Logic Flowchart

graph TD
    A["stack empty; maxArea = 0; append sentinel height 0"] --> B["for each i (height h)"]
    B --> C{"stack nonempty AND h < heights[top]?"}
    C -->|Yes| D["height = heights[pop()]"]
    D --> E["width = stack empty ? i : i - stack.peek() - 1"]
    E --> F["maxArea = max(maxArea, height * width)"]
    F --> C
    C -->|No| G["push i"]
    G --> H{"more?"}
    H -->|Yes| B
    H -->|No| I["Return maxArea"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the capstone stack. We keep an increasing stack of bar indices. When the current height is smaller than the top bar's, that bar's rectangle is bounded on the right: we pop it, take its height, and compute its width from the new stack top to the current index. The area updates the maximum. A trailing zero-height sentinel flushes the stack.

Code

public static int largestRectangleArea(int[] heights) {
    int n = heights.length, maxArea = 0;
    Deque<Integer> stack = new ArrayDeque<>();   // indices, heights increasing bottom-to-top
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];       // sentinel 0 flushes the stack at the end
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

// Usage:
// largestRectangleArea([2,1,5,6,2,3]) -> 10

This Java code keeps an increasing stack of bar indices. When the current height is smaller than the top bar's, it pops that bar, takes its height, and computes its width as the current index minus the new top index minus one, or the current index if the stack is empty. The area updates the maximum. A trailing zero-height sentinel flushes all remaining bars.

Step-by-Step Walkthrough

A frame-by-frame trace on heights = [2,1,5,6,2,3]:

graph LR
    F0["i0(2) push [0]<br/>i1(1)<2: pop 0 h2 w1 area2<br/>push [1]"]
    F1["i2(5) push, i3(6) push<br/>[1,2,3]"]
    F2["i4(2)<6: pop 3 h6 w(4-2-1)=1 area6<br/>2<5: pop 2 h5 w(4-1-1)=2 area10"]
    F3["push 4 [1,4]<br/>i5(3) push [1,4,5]"]
    F4["sentinel 0 flushes:<br/>pop 5 h3 w1, pop 4 h2 w4 area8, pop1 h1 w6 area6<br/>max=10"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough scans two, one, five, six, two, three. The one pops the two for area two. Five and six are pushed. The two then pops six for area six and five for area ten, the largest. After pushing the rest, a zero-height sentinel flushes the stack, where height two spans width four for area eight, but the maximum remains ten.

Result: 10.

Complexity

Time: O(n) - each bar pushed and popped exactly once. Space: O(n) - the stack.

Complexity Comparison

The monotonic stack is the definitive answer and the synthesis of the whole section: store indices, pop when a smaller bar arrives, and on each pop compute a rectangle whose height is the popped bar and whose width is the span between its previous-smaller and next-smaller boundaries. The sentinel-flush idiom ties it together.

Variations & Follow-ups

Why does popping on a smaller bar give the right width?

When bar t is popped because bar i (shorter) arrived, bar i is t's next-smaller boundary on the right, and the new stack top is t's previous-smaller boundary on the left. The widest rectangle of height heights[t] spans exactly between those boundaries - width i - newTop - 1 - because everything in that span is at least as tall as t.

Why the trailing sentinel of height 0?

Bars left on the stack at the end have no shorter bar to their right to trigger their pop. Appending a virtual bar of height 0 (at index n) is smaller than everything, forcing every remaining bar to be popped and measured. It avoids a separate cleanup loop.

How does this connect to Sum of Subarray Minimums?

Both compute, for each element, the span where it's the minimum/shortest via previous-smaller and next-smaller boundaries. There the spans feed a contribution sum; here they give a rectangle's width. The boundary-finding machinery is identical - the capstone reuses the section's central idea.

How is "Maximal Rectangle" (in a binary matrix) built on this?

Treat each matrix row as the base of a histogram whose bar heights are the counts of consecutive 1s above each column; run this algorithm per row and take the max. Largest Rectangle in Histogram is the kernel of that 2D problem - a direct, important follow-up.

What about edge cases?

• All equal heights ([3,3,3]): One big rectangle, height × n.
• Strictly increasing ([2,4]): The sentinel flush measures each → max is the best height × width (Example 2).
• Strictly decreasing: Each bar pops the previous immediately; widths grow leftward.
• Single bar / zero heights: Area is the bar's height (or 0).

Common Interview Pitfalls

• Wrong width formula. It's i - stack.peek() - 1 after popping, or i when the stack empties - off-by-one here is the classic bug.
• Forgetting the sentinel. Without the trailing 0, bars left on the stack are never measured.
• Using <= instead of <. Popping on equal heights still works but must be consistent; the clean form pops on strictly smaller and measures equal-height runs via the leftmost survivor.
• Storing heights instead of indices. Widths require positions; indices are essential.

Why This Problem Matters

Largest Rectangle in Histogram is the synthesis of the entire monotonic-stack section and a rite of passage in algorithm interviews. It fuses every technique you've built - indices for spans, the smaller-arrival pop rule, previous/next-smaller boundaries, and the sentinel-flush idiom - into one elegant O(n) sweep. It also unlocks a family of harder problems (Maximal Rectangle, skyline-style questions). If you can derive this from the template under pressure, you've truly internalized the pattern.

This completes Section 16 - Stacks, from the LIFO fundamentals and the standard problem family through the full monotonic-stack repertoire. You've seen the stack as a matcher, a simulator, an expression evaluator, an ordering engine, and a span-measuring machine. The next section, Section 17 - Queues, turns to the stack's mirror image: first-in-first-out processing, where the oldest element is the one you handle next - powering breadth-first traversal, sliding-window extremes (via the closely related monotonic deque), and stream-processing patterns that complement everything you've just learned.

Back to DSA Mastery - Interview Prep, End to End