Largest Rectangle in Histogram: A Step-by-Step Interview Walkthrough

Largest Rectangle in Histogram earns its status as a hard problem because while the brute force solution is obvious, the optimization is not, and the leap between them requires a genuinely clever data structure: the monotonic stack. The problem asks for the area of the largest rectangle that fits inside a histogram of bars. Most candidates can write the O(n²) "try every bar as the limiting height" solution, but getting to O(n) requires seeing that a stack can track exactly the information you need, exactly when you need it. Once you understand why a stack of increasing heights solves this, a whole family of "next smaller / next greater element" problems opens up.

Finding the largest area under a profile shows up across real domains. Data-visualization tools compute the largest uniform region under a bar chart for labeling or highlighting. Image processing finds the largest rectangle of uniform intensity in a row of pixels (and, extended to 2D, the Maximal Rectangle problem in binary matrices). Memory allocators and scheduling systems find the largest contiguous block available under a usage profile. Stock and signal analysis finds the widest span meeting a height threshold. Any time you have a sequence of heights and need the largest axis-aligned rectangle that fits beneath them, this is the problem.

Problem Statement

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 can be formed within the histogram.

The rectangle must be axis-aligned and fit entirely under the bars — its height is limited by the shortest bar it spans.

Example: 

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

result → 10

The largest rectangle spans bars at indices 2 and 3 (heights 5 and 6), limited to height 5 across width 2, for area 5 × 2 = 10.

Solution Summary

The optimal solution uses a monotonic increasing stack and runs in O(n) time and O(n) space. The key insight is that for each bar, the largest rectangle limited to that bar's height extends left and right until it hits a strictly shorter bar — so the real task is finding, for every bar, its nearest shorter neighbor on each side.

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: an array heights of non-negative integers, each a bar of width 1.

Output: a single integer — the area of the largest rectangle that fits under the bars.

Details to clarify:

• Can heights be zero? Yes, a zero-height bar contributes no area and effectively acts as a barrier splitting the histogram.

• Can the array be empty? Possibly; return 0 if so.

• Are all bars width 1? Yes, so a rectangle spanning k consecutive bars has width k, and its area is k × (the shortest bar in that span).

• Does the rectangle have to align to bar boundaries? Yes, it's made of whole bars, so its width is an integer count of consecutive bars.

• Can heights be negative? No, heights are non-negative, which matters for our reasoning about boundaries.

The thing to flag is what limits a rectangle's height: the shortest bar it spans. A rectangle covering bars of heights [5, 6] can only be height 5. The 6 gets "clipped" down to 5 because the rectangle must fit under both. In other words, every rectangle is some height, extended as far as it can go before it hits something shorter.

2. Identify the Category of the Question

A few signals jump out:

• The data is a sequence, and we're looking for an optimal contiguous span.

• The value of each candidate (a rectangle's area) depends on finding boundaries — how far a given height extends before being blocked.

• Those boundaries are defined by the nearest shorter bar on each side.

That combination — for each element, find the nearest smaller element to its left and right — is the fingerprint of the monotonic stack pattern. The same family as Next Greater Element, Daily Temperatures, and Trapping Rain Water. The core realization, which we'll build toward, is that "nearest shorter bar on each side" can be computed for all bars in a single linear pass using a stack that maintains a sorted (monotonic) invariant, rather than searching outward from each bar independently.

3. Brute Force Solution

Let's think about the naive approach to understand the problem. A natural brute force is: treat each bar as the limiting height, and find how wide a rectangle of that height can stretch.

For a bar at index i with height heights[i], we expand left and right as long as the neighboring bars are at least as tall as heights[i] (they can support a rectangle of this height).

The moment we hit a shorter bar, we stop, and that becomes our edge. Since we've height to heights[i] , a shorter bar would result in a gap where the rectangle is not entirely under the bars, which is against the rules.

So the width is the span we covered, and the area is heights[i] × width. Take the maximum over all bars.

best = 0
for i in 0..n-1:
    left = i, right = i
    while left > 0 and heights[left - 1] >= heights[i]:  left--
    while right < n-1 and heights[right + 1] >= heights[i]: right++
    width = right - left + 1
    best = max(best, heights[i] * width)
return best

This is correct — every possible largest rectangle is limited by some bar's height, so trying each bar as the limiter covers all cases. But for each bar we might scan the entire array expanding left and right, giving O(n²) time.

The brute force clarifies the real task, though. For each bar, what we're really computing is: how far left until a strictly shorter bar, and how far right until a strictly shorter bar? Those two boundaries are all we need. The waste is that we recompute these boundaries from scratch for every bar, rescanning the same regions over and over. The optimization question is sharp: can we find every bar's nearest-shorter-neighbor on both sides without rescanning? That question points directly at the monotonic stack.

4. Brainstorm More Solutions

Step 1: Turn the boundary search into two clean passes

The brute force showed us that each bar's rectangle is limited by the nearest strictly shorter bar on its left and on its right. The slow part was recomputing those boundaries from scratch for every bar. What if we just pre-compute all the left boundaries in one sweep, and all the right boundaries in another, and then combine them?

We can keep an array left[] where left[i] is the index of the nearest shorter bar to the left of i. For each i, we start at i - 1 and repeatedly jump to left[that index] until we land on a bar shorter than heights[i] (or fall off the front, meaning the boundary is -1). Then we do the mirror image in a second pass, scanning right to left to fill a right[] array. Finally, a third pass computes heights[i] × (right[i] - left[i] - 1) for every bar and takes the maximum.

This works and runs in O(n) — each bar's boundary is found by following jump-pointers that collectively never re-traverse the same ground, so the amortized cost is linear. The downside is that it makes three passes and maintains two auxiliary arrays. We should think about whether there's a way to do this in just one pass.

Step 2: Pin down exactly what each bar needs

Let's make the brute-force insight precise. For the rectangle limited to bar i's height, the rectangle extends:

• Leftward until just before the first bar shorter than heights[i].

• Rightward until just before the first bar shorter than heights[i].

So if we knew, for bar i, the index of the nearest strictly shorter bar to its left (call it L) and the nearest strictly shorter bar to its right (call it R), the rectangle's width would be everything strictly between them: R - L - 1. The area would be heights[i] × (R - L - 1).

That's the whole problem reduced to a cleaner sub-problem: for every bar, find its nearest strictly shorter neighbor on the left and on the right. If we can compute those two arrays efficiently, the answer is a single pass computing heights[i] × (R[i] - L[i] - 1) and taking the max. So the question is how to find nearest-shorter-neighbors fast.

Step 3: Notice what makes the brute-force search wasteful

Why is searching for the nearest shorter bar slow in the brute force? Because each bar searches independently, redoing work its neighbors already did. Let's look for a structure we can exploit.

Suppose we're scanning left to right, and we've just passed a sequence of bars. Think about which previous bars could ever serve as the "nearest shorter left neighbor" for some future bar. Consider two earlier bars, a before b, where a is taller than or equal to b. For any future bar, if it's looking leftward for the nearest shorter bar, b will always block its view of a — because b comes after a and is shorter, so any future bar reaches b before it could ever reach a. That means a is now useless as a left-boundary candidate for anything in the future/

This is the key observation: once a bar is followed by a later bar that's shorter or equal, the earlier (taller) bar can be discarded from future boundary searches. The only bars worth remembering as potential left-boundaries are ones in strictly increasing height order — because each shorter-or-equal bar wipes out the taller ones behind it. That "keep only an increasing sequence, discard the shadowed ones" behavior is exactly what a monotonic stack maintains.

Step 4: Build the monotonic stack

Let's maintain a stack of bar indices whose heights are strictly increasing from bottom to top. We process bars left to right. For each new bar, before pushing it, we remove any bars on the stack that are taller than or equal to the current bar — because, by Step 2, the current bar shadows them; they can never be a boundary for anything further right.

Now let's reason about what we actually know at the instant we pop a bar — because it turns out to be exactly the two boundaries we needed, and that's not a coincidence.

We only pop a bar when the current bar is shorter than it. So ask: what is the current bar, relative to the bar we're popping? It's the first bar we've encountered, scanning left to right, that's shorter than the popped bar — everything in between was taller (or it would have triggered a pop earlier). That's the definition of the popped bar's nearest shorter neighbor on the right. We didn't search for it; it announced itself by being the thing that caused the pop.

Now look at what remains on the stack underneath. After we remove the popped bar, some earlier bar is the new the top.

What can we say about that new top?

First, the new top is shorter than the popped bar: the stack keeps heights strictly increasing from bottom to top, so whatever sits below the popped bar must be shorter than it.

Second, there's nothing shorter in between. There can't be any shorter bar between the new top and the popped bar, because such a bar would have popped the bar we just removed at the moment it arrived — so the popped bar wouldn't have survived on the stack for us to pop now. Since a bar only gets removed when a taller survivor remains beneath it, the new top outlasting all of them means the new top is shorter than every one of them.

Putting those together: the new top is shorter than the popped bar, and everything between them is taller. That makes the new top the first bar to the popped bar's left that's shorter than it — its nearest shorter neighbor on the left, discovered for free the moment we pop.

So both boundaries fall out of the stack's structure for free, at the exact moment of the pop: the current bar on the right, the new stack top on the left. The stack has been quietly maintaining precisely the information we needed, and we never had to scan outward to find it.

Step 5: Work out the width calculation

When we pop bar p (with height heights[p]) because the current bar at index i is shorter, we compute p's rectangle:

• The right boundary is i (the current bar, the first strictly-shorter bar to the right).

• The left boundary is the new stack top after popping — call it stack.top.

• If the stack is now empty, it means there was no shorter bar to the left at all; the rectangle extends all the way to the start, so we treat the left boundary as index -1.

• The width is everything strictly between the two boundaries: i - stack.top - 1 (or i if the stack is empty, which is i - (-1) - 1).

The area is heights[p] × width. We track the maximum across all pops.

Step 6: Handle the leftover stack at the end

After processing all bars, the stack may still hold some indices — bars that never found a shorter bar to their right (their heights increased all the way to the end, or trailed off without anything shorter following). These bars have a right boundary of n (the end of the histogram — nothing shorter ever appeared to their right).

Can we handle this edge case without adding special case logic? Imagine appending a sentinel bar of height 0 at the end of the histogram. Since 0 is shorter than every real bar, it forces every remaining bar to be popped and have its area computed, with the right boundary correctly set to n.

We can either physically append a 0 or just run one extra iteration treating the height as 0.

Step 7: Walk through the example

Let's trace heights = [2, 1, 5, 6, 2, 3], using a sentinel 0 at the end (index 6).

Stack holds indices; heights increase bottom to top. Track maxArea = 0.

• i=0, h=2: stack empty, push 0. Stack: [0] (heights: [2]).

• i=1, h=1: top is index 0 (h=2) ≥ 1, pop it. Right boundary = 1, stack now empty so left boundary = -1, width = 1 - (-1) - 1 = 1. Area = 2 × 1 = 2. maxArea = 2. Now push 1. Stack: [1] (heights: [1]).

• i=2, h=5: top is index 1 (h=1) < 5, no pop. Push 2. Stack: [1, 2] (heights: [1, 5]).

• i=3, h=6: top is index 2 (h=5) < 6, no pop. Push 3. Stack: [1, 2, 3] (heights: [1, 5, 6]).

• i=4, h=2: top is index 3 (h=6) ≥ 2, pop. Right=4, new top is index 2, left=2, width = 4 - 2 - 1 = 1. Area = 6 × 1 = 6. maxArea = 6. Top is now index 2 (h=5) ≥ 2, pop. Right=4, new top index 1, left=1, width = 4 - 1 - 1 = 2. Area = 5 × 2 = 10. maxArea = 10. Top is index 1 (h=1) < 2, stop. Push 4. Stack: [1, 4] (heights: [1, 2]).

• i=5, h=3: top index 4 (h=2) < 3, no pop. Push 5. Stack: [1, 4, 5] (heights: [1, 2, 3]).

• i=6, h=0 (sentinel): pop index 5 (h=3): right=6, new top index 4, left=4, width = 6-4-1 = 1, area = 3×1 = 3. Pop index 4 (h=2): right=6, new top index 1, left=1, width = 6-1-1 = 4, area = 2×4 = 8. Pop index 1 (h=1): right=6, stack empty, left=-1, width = 6-(-1)-1 = 6, area = 1×6 = 6. Stack empty.

Final maxArea = 10. Correct — the height-5 rectangle across indices 2–3.

Step 8: Complexity

Let n be the number of bars. Let's derive the cost from how the stack is used.

The main loop processes each bar once. Each bar is pushed onto the stack exactly once, and popped exactly once. So the total number of push and pop operations across the whole algorithm is at most 2n. Every other operation per step is O(1) (computing a width, comparing to the max).

So the total time is O(n). This "each element is pushed and popped once, so the total work is linear" argument is the signature complexity analysis for monotonic-stack algorithms; recognize it and reuse it.

Space is O(n) for the stack, which in the worst case (strictly increasing heights) holds every bar before any pops occur.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Try each bar as limiter, expand outward	O(n²)	O(1)	Never for large inputs — but it frames the boundary insight
Precompute left/right boundaries with two stack passes	O(n)	O(n)	Clear and correct; slightly more code than the one-pass version
Single monotonic-stack pass	O(n)	O(n)	My default — computes boundaries and areas in one sweep

The monotonic-stack solution is the intended answer. There's a two-pass variant (compute the nearest-shorter-left array in one pass, the nearest-shorter-right array in another, then combine) that some find easier to reason about; it's the same complexity and a fine choice if the one-pass version's "compute area at pop time" feels too dense to write correctly under pressure. I'd mention both and lead with the one-pass version for its elegance.

6. Pseudocode

stack = empty stack of indices    # heights strictly increasing bottom→top
maxArea = 0
append a sentinel height of 0 to the end of heights

for i in 0 .. n (inclusive of sentinel):
    while stack not empty and heights[i] < heights[stack.top]:
        poppedHeight = heights[stack.pop()]
        # right boundary is i; left boundary is the new top (or -1 if empty)
        leftBoundary = stack.empty ? -1 : stack.top
        width = i - leftBoundary - 1
        maxArea = max(maxArea, poppedHeight * width)
    stack.push(i)

return maxArea

7. Edge Cases

Things to verify before claiming we're done:

• Empty array → no bars, return 0. (Guard at the top if needed.)

• Single bar ([7]) → the sentinel pops it with width 1, area 7. ✓

• All equal heights ([3, 3, 3]) → each bar shadows the previous (equal counts as shadowing), and the full-width rectangle of height 3 is found. Area 9. ✓

• Strictly increasing ([1, 2, 3]) → nothing pops until the sentinel, then all pop in sequence; the best rectangle is found during draining. ✓

• Strictly decreasing ([3, 2, 1]) → each bar pops the previous immediately; boundaries computed step by step. ✓

• A zero-height bar in the middle ([2, 0, 2]) → the 0 acts as a barrier, forcing pops and splitting the histogram, so no rectangle spans across it. ✓

The "all equal heights" case is worth attention: we pop when the current bar is shorter than or equal to the stack top (using < on the current vs. top, i.e., popping when heights[i] < heights[top] is false-inclusive of equal needs care). The standard formulation pops on strictly-less and lets equal heights push, which still yields the correct maximum because the full width gets measured when the eventual shorter bar (or sentinel) triggers the pops.

8. Full Code

import java.util.*;

public class LargestRectangleInHistogram {

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

        // Iterate one past the end; treat index n as a sentinel 
        // bar of height 0, which is shorter than every real bar 
        // and forces all remaining pops.
        for (int i = 0; i <= n; i++) {
            int currHeight = (i == n) ? 0 : heights[i];

            // Pop every bar taller than the current one — the 
            // current bar is their nearest shorter neighbor on the 
            // right.
            while (!stack.isEmpty() && currHeight < heights[stack.peek()]) {
                int poppedHeight = heights[stack.pop()];

                // After popping, the new top is the popped bar's 
                // nearest shorter neighbor on the left (or -1 if 
                // the stack is now empty).
                int leftBoundary = stack.isEmpty() ? -1 : stack.peek();
                int width = i - leftBoundary - 1;

                maxArea = Math.max(maxArea, poppedHeight * width);
            }

            stack.push(i);
        }

        return maxArea;
    }
}

9. Test the Code

// Canonical example
System.out.println(largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));  // 10

// Single bar
System.out.println(largestRectangleArea(new int[]{7}));                 // 7

// All equal — full-width rectangle
System.out.println(largestRectangleArea(new int[]{3, 3, 3}));           // 9

// Strictly increasing
System.out.println(largestRectangleArea(new int[]{1, 2, 3, 4, 5}));     // 9 (height 3 × width 3)

// Strictly decreasing
System.out.println(largestRectangleArea(new int[]{5, 4, 3, 2, 1}));     // 9 (height 3 × width 3)

// Zero-height barrier in the middle
System.out.println(largestRectangleArea(new int[]{2, 0, 2}));           // 2

// Classic tricky case
System.out.println(largestRectangleArea(new int[]{2, 1, 2}));           // 3 (height 1 × width 3)

These hit the meaningful cases: the canonical example, a single bar, all-equal heights, monotonic increasing and decreasing inputs (which exercise the "nothing pops until the end" and "everything pops immediately" extremes), a zero barrier, and the [2, 1, 2] case that catches solutions which forget a short bar can anchor a wide rectangle (the height-1 rectangle spans all three bars for area 3, beating either height-2 single bar).

10. Key Lessons

• When a problem asks for an optimal span whose value depends on boundaries (here, the nearest shorter bar on each side), the monotonic stack is often the tool. It computes those boundaries for every element in a single linear pass instead of searching outward from each element independently.

• The brute force here reveals the real sub-problem: find each bar's nearest strictly-shorter neighbor on the left and right. Reducing a problem to a clean, reusable sub-problem ("nearest smaller element") is often more valuable than the specific answer, because that sub-problem recurs across many questions.

• A monotonic stack works by discarding elements that can never again be the answer. Once a bar is shadowed by a later shorter-or-equal bar, it's useless as a future boundary, so we pop it. Understanding what gets discarded and why is the heart of the pattern.

• The linear-time argument for stack algorithms is "each element is pushed once and popped once, so total work is O(n) despite the nested loop." Recognize this accounting — it's how you justify O(n) for the whole monotonic-stack family.

• Sentinels eliminate cleanup code. Appending a height-0 bar forces every remaining stack element to be popped with the correct right boundary, folding the end-of-array draining into the main loop. Reach for a sentinel when boundary handling threatens to spawn special cases.

The thing that makes Largest Rectangle in Histogram click is seeing that every rectangle is "a height extended until it's blocked on both sides," and that the blocking bars are exactly each bar's nearest shorter neighbors. Once you realize a monotonic stack discovers both of those boundaries for free at the instant it pops a bar, the O(n²) boundary search collapses into a single elegant pass. That insight — replacing repeated outward searches with one stack that remembers only what still matters — is the rite of passage into the entire monotonic-stack family, from Daily Temperatures to Trapping Rain Water to Maximal Rectangle.

Frequently Asked Questions

What is the time complexity of the largest rectangle in histogram problem? The optimal solution runs in O(n) time and O(n) space using a monotonic stack. Although the algorithm has a nested loop, each bar is pushed onto the stack exactly once and popped exactly once, so the total number of stack operations is at most 2n — keeping the overall work linear.

Why doesn't the brute-force approach work efficiently? The brute force treats each bar as a limiting height and expands left and right to find its boundaries, which takes O(n²) time because it rescans the same regions repeatedly. It's correct but too slow for large inputs, and it wastes work that a monotonic stack computes once.

What is a monotonic stack and why is it used here? A monotonic stack is a stack whose elements stay in sorted order (here, bar heights strictly increasing from bottom to top), achieved by discarding elements that violate the order before pushing a new one. It's used because popping a bar reveals both its nearest shorter neighbor on the right (the current bar) and on the left (the new stack top) in O(1), which is exactly the boundary information each rectangle needs.

How do you calculate the width of each rectangle? The width is the distance strictly between a bar's two nearest shorter neighbors: rightBoundary - leftBoundary - 1. When a bar is popped, the right boundary is the current index causing the pop, and the left boundary is the index now on top of the stack (or -1 if the stack is empty, meaning the rectangle extends to the histogram's start).

Why add a sentinel bar of height zero at the end? A height-0 sentinel is shorter than every real bar, so it forces every bar still on the stack to be popped and have its area computed, with the right boundary correctly set to the histogram's end. This folds the end-of-loop cleanup into the main pass, eliminating separate draining logic and a class of off-by-one bugs.

Good Luck and Happy Coding!