Largest Rectangle in Histogram

The hard part is rarely choosing a rectangle height. It is proving how far that height can extend.

For each bar, we need the widest contiguous span in which every bar is at least as tall. A left-to-right scan with a monotonic stack resolves that span exactly when a shorter bar appears. Each index is pushed once, popped at most once, and the complete solution runs in O(n) time.

Define the rectangle boundary obligation

The input is an array of non-negative bar heights. Every bar has width 1, rectangles must use contiguous bars, and the result is the maximum rectangular area.

Fix a bar at index i with height heights[i]. Treat that height as the rectangle's limiting height. The rectangle can extend left and right while every included bar remains at least that tall.

The first strictly shorter bar on each side stops the extension:

left_smaller  = nearest index left of i with height < heights[i]
right_smaller = nearest index right of i with height < heights[i]

The blockers themselves cannot be included, so the width is:

width = right_smaller - left_smaller - 1
area  = heights[i] * width

If no smaller bar exists on one side, use the conceptual boundary -1 on the left or n on the right.

For:

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

the bar of height 5 at index 2 is bounded by:

• index 1, whose height is 1, on the left
• index 4, whose height is 2, on the right

Therefore:

width = 4 - 1 - 1 = 2
area = 5 * 2 = 10

The tallest bar has height 6, but it can only use width 1. Height alone does not determine the answer. The boundary determines the answer.

The direct solution direction is:

1. Scan from left to right.
2. Keep unresolved candidate bars in a stack ordered by height.
3. When the current bar is shorter than the stack top, finalize the popped bar's widest possible rectangle.
4. Flush the remaining candidates with a virtual height-0 bar at the end.

The stack is a boundary-reuse mechanism. It prevents us from searching the same territory repeatedly.

Establish the brute-force baseline

A straightforward solution treats every bar as the rectangle's minimum height:

1. Start at the bar.
2. Scan left while heights remain at least as large.
3. Scan right while heights remain at least as large.
4. Compute the resulting area.

On increasing, decreasing, or plateau-heavy inputs, this repeats the same work for many bars. A bar inspected while expanding one candidate is inspected again while expanding another. In the worst case, the total work is:

1 + 2 + 3 + ... + n = O(n²)

The problem is not the area formula. The problem is repeated boundary discovery.

We need to remember which bars are still waiting for their first smaller value on the right. That is exactly the unresolved state a stack can represent.

Derive the increasing candidate stack

Store indices, not heights.

The height at an index is available in heights, but the index is needed to calculate the width. An index also lets the stack preserve left-to-right order.

Use this policy:

pop while heights[stack[-1]] > current_height

Equal heights stay in the stack. This strict > choice is deliberate; the equal-height consequences are discussed later.

The stack invariant is:

Indices in the stack are ordered from left to right, and their corresponding heights are nondecreasing.

Every index in the stack is unresolved. No strictly shorter bar has appeared to its right yet.

Suppose the current index is i, and the stack top is j:

heights[j] > heights[i]

Then the current bar at i is the first strictly shorter bar to the right of j. The right boundary for j is now known.

Pop j. After popping, the new stack top is the nearest surviving candidate to the left of j with a smaller height. Call it left_boundary. If the stack is empty, the left boundary is the conceptual index -1.

The width is the number of indices strictly between the boundaries:

width = i - left_boundary - 1
area = heights[j] * width

Why does the current bar need to be processed before being pushed? Because it is a right-side blocker for every taller candidate currently on the stack. Resolve those candidates first. Then push the current index as a new unresolved candidate.

The algorithm's state is small because every variable has a job:

State	Obligation
stack	Indices whose right boundary is not known
current_height	The height that may resolve taller candidates
i	The right boundary for every bar popped now
stack[-1] after a pop	The popped bar's left boundary
max_area	Best finalized rectangle so far

Prove why a popped bar is finished

A stack implementation is only useful in an interview if you can explain why a pop is final. There are two parts to the proof.

The right boundary is final

Assume index j remains in the stack until the current index i.

Every processed bar between j and i had height at least heights[j]; otherwise j would already have been popped. The current bar has smaller height, so it is the first strictly shorter bar to the right.

Thus i is the earliest possible right blocker for a rectangle at height heights[j].

The left boundary is correct

When j is popped, taller candidates that sat between the surviving stack top and j have already been removed. The remaining stack top, if one exists, is the nearest index to the left whose height is smaller than heights[j].

So the interval between the two blockers is maximal for height heights[j].

The width is therefore:

i - stack[-1] - 1

when the stack remains nonempty, or:

i

when every earlier candidate was popped.

Why cannot the popped bar return?

Once j encounters a shorter bar at i, any future rectangle containing j and extending farther right must also contain i. But i is shorter than heights[j], so such a rectangle cannot maintain height heights[j].

The current shorter bar permanently dominates every future right extension for j. The candidate is finished.

That is the key monotonic-stack idea: a violation does not merely trigger an operation. It destroys the candidate's remaining possibilities.

Why the total work is linear

Each real index is:

• pushed once
• popped at most once

The while loop can pop many indices during one iteration, but those indices cannot be popped again. Across the complete scan, there are at most n pushes and n pops.

Therefore:

time  = O(n)
space = O(n)

The nested loop is amortized linear. Count the lifetime of each index, not the visual nesting of the code.

Flush unresolved bars with a sentinel

A shorter real bar may never arrive for an increasing suffix.

For example:

[1, 2, 3]

Every bar can extend to the end, but the scan has no real next bar that forces those candidates to resolve.

Add a virtual height-0 event at index n. Because all valid heights are non-negative, this event is shorter than every positive-height candidate and flushes the stack.

The sentinel is a control-flow signal, not a real histogram bar:

current_height = 0 if i == n else heights[i]

The width calculation has two cases:

if stack:
    width = i - stack[-1] - 1
else:
    width = i

If the stack becomes empty at the sentinel, the popped bar spans indices 0 through i - 1, so its width is i.

If a smaller bar remains on the stack, that bar is the left blocker, and the popped bar spans from stack[-1] + 1 through i - 1.

There is one implementation trap: never evaluate heights[i] during the sentinel iteration. Since i == n is outside the array, the current height must be selected before the pop condition checks the stack.

Also push only real indices. The sentinel index must not enter the stack, or later code may attempt to read heights[n].

Make equal heights a deliberate choice

Equal heights are where otherwise plausible implementations become inconsistent.

There are two common policies:

heights[stack[-1]] > current_height

Keep equal-height bars separate.

heights[stack[-1]] >= current_height

Collapse equal-height bars while processing the current bar.

Both policies can work. The failure comes from mixing their assumptions across the pop condition, invariant, and width calculation.

This article uses strict > and retains equal heights.

For:

[2, 2, 2]

the stack becomes [0, 1, 2]. At the sentinel:

• pop index 2, width 1, area 2
• pop index 1, width 2, area 4
• pop index 0, width 3, area 6

The earliest equal-height bar eventually becomes the representative that sees the full width.

For:

[2, 2, 1]

the height-1 bar resolves all three height-2 candidates. The final popped candidate covers the full width before the shorter bar:

width = 3
area = 2 * 3 = 6

If you choose >= instead, equal bars are collapsed as you scan. That can also produce the correct maximum, but the exact meaning of the surviving index changes. In an interview, state the policy before coding:

I will keep equal heights and pop only strictly taller bars. The stack is nondecreasing, and a shorter bar resolves all taller candidates.

That one sentence prevents a large class of boundary bugs.

Dry-run the stack on the canonical input

Use:

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

The stack contains indices. The values shown in parentheses are their heights.

Index	Height	Stack before	Popped work	Stack after
0	2	[]	—	[0(2)]
1	1	[0(2)]	Pop 0: left -1, width 1, area 2	[1(1)]
2	5	[1(1)]	—	[1(1), 2(5)]
3	6	[1(1), 2(5)]	—	[1(1), 2(5), 3(6)]
4	2	[1(1), 2(5), 3(6)]	Pop 3: left 2, width 1, area 6	[1(1), 2(5)]
			Pop 2: left 1, width 2, area 10	[1(1)]
			Push index 4	[1(1), 4(2)]
5	3	[1(1), 4(2)]	—	[1(1), 4(2), 5(3)]
6	0	[1(1), 4(2), 5(3)]	Pop 5: width 1, area 3	[1(1), 4(2)]
			Pop 4: left 1, width 4, area 8	[1(1)]
			Pop 1: left -1, width 6, area 6	[]

The important event is index 4, height 2.

First, height 6 is finalized with width 1. Then height 5 is finalized with:

left boundary  = 1
right boundary = 4
width          = 4 - 1 - 1 = 2
area           = 5 * 2 = 10

The new stack top after popping 6 supplies the left boundary for 5. The stack is doing two jobs at once: it identifies the right blocker through the current index and reveals the left blocker through the surviving top.

Implement the one-pass Python solution

The code should look like the proof. If the variable names hide the boundary logic, the implementation becomes harder to debug.

def largest_rectangle_area(heights: list[int]) -> int:
    n = len(heights)
    stack: list[int] = []
    max_area = 0

    for i in range(n + 1):
        # Index n is a virtual height-0 bar used to flush the stack.
        current_height = 0 if i == n else heights[i]

        while stack and heights[stack[-1]] > current_height:
            bar_index = stack.pop()
            bar_height = heights[bar_index]

            left_boundary = stack[-1] if stack else -1
            width = i - left_boundary - 1
            area = bar_height * width

            max_area = max(max_area, area)

        # The sentinel is a signal, not a real bar.
        if i < n:
            stack.append(i)

    return max_area

A useful debugging checklist:

1. Check the invariant. Before each push, stack heights should be nondecreasing.
2. Inspect every pop. The current index must be the popped bar's first strictly shorter bar on the right.
3. Inspect the new top. After popping, it is the nearest surviving smaller bar on the left, or -1.
4. Check excluded boundaries. The blockers are not part of the rectangle, which is why the width subtracts 1.
5. Test the sentinel separately. It must flush candidates without being pushed or dereferenced.
6. Test equal heights. The code uses >, so equal-height indices remain in the stack.

This is the kind of implementation I prefer in an interview: the code carries the argument. There is no separate left-boundary array, right-boundary array, or post-processing pass to obscure when a candidate becomes final.

Audit complexity and edge cases

For n bars, the algorithm performs one scan plus stack operations. Each index enters the stack once and leaves it at most once.

Therefore:

Time:  O(n)
Space: O(n)

The stack is auxiliary space. Apart from it, the algorithm uses constant working state.

Test the boundary cases that expose incorrect assumptions:

Input shape	What it checks
[7]	Single-bar width
[0, 0, 0]	Zero areas and sentinel behavior
[1, 2, 3]	Increasing suffix and full flush
[3, 2, 1]	Repeated pops during real iterations
[2, 2, 2]	Equal-height policy
[2, 2, 1]	Equal heights followed by a blocker
[0, 3, 4, 0]	Independent regions separated by zero
Maximum-length input	Linear-time and linear-space accounting

Most off-by-one errors come from treating a blocker as part of the rectangle. It is not. If the left blocker is left_boundary and the right blocker is right_boundary, the valid indices are:

left_boundary + 1 ... right_boundary - 1

so:

width = right_boundary - left_boundary - 1

The stack is necessary when the input can be large and the same boundary searches would otherwise repeat. For a tiny input, a brute-force scan may be simpler and perfectly adequate. In an interview with the stated bounds, however, the stack is the scale choice: it converts repeated searching into permanent elimination.

The transferable recognition rule

When each candidate defines a contiguous range that ends at the first smaller value, look for a monotonic stack.

The reusable derivation is:

1. Choose what each candidate means—in this problem, a bar treated as the rectangle height.
2. Identify the event that finalizes it—the first strictly shorter bar on the right.
3. Maintain unresolved candidates in monotonic order.
4. On a violation, pop candidates that can no longer extend.
5. Use the current index as the right boundary and the new stack top as the left boundary.
6. Flush unresolved candidates with an explicit end sentinel.
7. Decide how equal values behave before writing the comparison.

Before coding, say the invariant, the equal-height policy, the sentinel plan, and the width formula out loud. Then the implementation is mostly bookkeeping.

The stack does not guess the largest rectangle. It waits until each candidate's future is constrained enough to measure. That is the pattern to carry into the next problem.