DSA-046 · Increasing stack with equal-height ownership transfer

Largest Rectangle in Histogram

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 21852 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the maximum area of a rectangle formed by consecutive unit-width histogram bars.

heights is non-null with 0–100,000 values in 0..Integer.MAX_VALUE. Both methods throw IllegalArgumentException for a negative height. Preserve the input.
Return a long area. A rectangle uses a contiguous nonempty span and has height at most every bar in that span. Empty input and all-zero input return zero. The maximum area under the bounds fits long but may exceed int.
The stack uses strictly increasing heights by popping on ≥. An equal-height pop evaluates a valid partial span and transfers future ownership to the newer equal bar; it is not claimed to finalize the widest span yet. A virtual -1 height at i=n flushes all real bars and is never pushed or read from the source array.

Examples

Input: [2,1,5,6,2,3]
Output: 10
Bars at indices two and three support height five across width two.
Input: [2,2,2]
Output: 6
Equal-height ownership reaches the full width when the final representative is flushed.

Before you start

Stack top versus bottom and last-in-first-out order
Loop invariants, checked arithmetic, and amortized analysis

Recognize the structure

A lower incoming bar ends the rightward reach of taller pending bars. The stack remembers the previous lower boundary needed to compute width when a bar’s candidate is popped. Equal-height handling must preserve the possibility of the widest plateau rectangle.

Try before revealing

Hint 1

When does a new bar prove a pending height cannot continue right?

Hint 2

After a pop, which two boundaries enclose its valid span?

Hint 3

Compute height*(i-left-1), transfer equal representatives, and flush with a virtual sentinel.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate every span and its minimum

For each left boundary, extend right while retaining the minimum height, and compare minimum*(right-left+1) in long. For [2,1,2], spans of width one yield two, the full width has minimum one and area three, and the answer is three. This O(n²) baseline states the rectangle definition directly.

Improve the baseline

Keep increasing candidate heights

Store source indices whose heights strictly increase from bottom to top. Before pushing the next real bar, pop every candidate with height≥current.

Compute a popped candidate’s width

After popping bar, let left be the new top index or -1. The valid candidate span is [left+1,i), with width i-left-1 and height heights[bar]. Compare its long area with best.

Transfer equals and flush safely

If current equals the popped height, the newer index inherits the chance to span past the old one because the same lower stack boundary remains. At i=n use a virtual -1 current value to pop everything, but never index heights[n] or push n.

Why it is correct

Stack invariant

After each real insertion, stored indices increase and their heights strictly increase. Pending candidates have no smaller bar encountered to their right that would have finalized their reach; equal candidates are replaced by a newer representative.

Valid spans and tie ownership

For a popped height h, bars after the new lower top through i-1 all have height≥h, so the evaluated rectangle is valid. If current<h, the current boundary is genuinely lower and the width is maximal for that representative. If current==h, the evaluated width may be partial; pushing the equal replacement preserves the same earlier lower boundary for a later wider candidate.

Global optimum and termination

Choose the minimum height of an optimal span. Equal representatives transfer its opportunity without losing the span’s left boundary, and the representative is eventually popped by a strictly lower bar or the virtual sentinel. Its candidate covers at least that optimal span, so best cannot miss the optimum. Every evaluated span is valid, preventing overestimation. Each real index enters once and leaves once, giving linear stack work.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayDeque;
public final class Solution {
    private static void validate(int[] heights) {
        for (int height : heights) if (height < 0) throw new IllegalArgumentException("nonnegative heights required");
    }
    public static long largestRectangleArea(int[] heights) {
        validate(heights);
        ArrayDeque<Integer> increasing = new ArrayDeque<>();
        long best = 0;
        for (int i = 0; i <= heights.length; i++) {
            int current = i == heights.length ? -1 : heights[i];
            while (!increasing.isEmpty() && heights[increasing.peek()] >= current) {
                int bar = increasing.pop();
                int left = increasing.isEmpty() ? -1 : increasing.peek();
                long area = (long) heights[bar] * (i - left - 1);
                best = Math.max(best, area);
            }
            if (i < heights.length) increasing.push(i);
        }
        return best;
    }
    public static long baseline(int[] heights) {
        validate(heights);
        long best = 0;
        for (int left = 0; left < heights.length; left++) {
            int minimum = Integer.MAX_VALUE;
            for (int right = left; right < heights.length; right++) {
                minimum = Math.min(minimum, heights[right]);
                best = Math.max(best, (long) minimum * (right - left + 1));
            }
        }
        return best;
    }
}

Read the meaningful blocks

Widen before multiplying

(long)height*width preserves areas such as two maximum-height bars, which exceed int.

The width excludes boundaries

The new lower stack top and current index are outside the candidate span; width is i-left-1, not i-left.

Keep sentinel access separate

The conditional expression chooses -1 when i==n, avoiding any heights[n] access. The sentinel is not a source bar and is never pushed.

Complexity

O(n) time including validation and amortized stack work. O(n) auxiliary indices, with one long result; the input is unchanged.

The all-span minimum baseline takes O(n²) time and O(1) other workspace. Tests independently examine height thresholds and longest supporting runs, including wide areas and 100,000 maximum-height bars.

Exact-state walkthroughs

Reveal normal and boundary traces

Pop completed spans at smaller right boundaries

Input: [2,1,5,6,2,3] · Result: 10

Step 1 of 22: Start with no pending histogram spans.

Pending indices will have strictly increasing heights after each real insertion.

Original array positions

0: 2
1: 1
2: 5
3: 6
4: 2
5: 3

Histogram bars and the current candidate span

Best area so far: 0.

Increasing-height candidates — bottom to top

Empty at this step.

State after this step
Variable	Value
values	`[2,1,5,6,2,3]`
increasingIndices	`[]`
best	`0`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 public final class Solution {
 3     private static void validate(int[] heights) {
 4         for (int height : heights) if (height < 0) throw new IllegalArgumentException("nonnegative heights required");
 5     }
 6     public static long largestRectangleArea(int[] heights) {
 7         validate(heights);
 8         ArrayDeque<Integer> increasing = new ArrayDeque<>();
 9         long best = 0;
10         for (int i = 0; i <= heights.length; i++) {
11             int current = i == heights.length ? -1 : heights[i];
12             while (!increasing.isEmpty() && heights[increasing.peek()] >= current) {
13                 int bar = increasing.pop();
14                 int left = increasing.isEmpty() ? -1 : increasing.peek();
15                 long area = (long) heights[bar] * (i - left - 1);
16                 best = Math.max(best, area);
17             }
18             if (i < heights.length) increasing.push(i);
19         }
20         return best;
21     }
22     public static long baseline(int[] heights) {
23         validate(heights);
24         long best = 0;
25         for (int left = 0; left < heights.length; left++) {
26             int minimum = Integer.MAX_VALUE;
27             for (int right = left; right < heights.length; right++) {
28                 minimum = Math.min(minimum, heights[right]);
29                 best = Math.max(best, (long) minimum * (right - left + 1));
30             }
31         }
32         return best;
33     }
34 }
35

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with no pending histogram spans.
Pending indices will have strictly increasing heights after each real insertion.
values
[2,1,5,6,2,3]
increasingIndices
[]
best
0
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,1,5,6,2,3]
i
0
current
2
increasingIndices
[]
best
0
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,1,5,6,2,3]
i
0
current
2
increasingIndices
[0]
best
0
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,1,5,6,2,3]
i
1
current
1
increasingIndices
[0]
best
0
Finalize a span at a genuinely smaller right boundary.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,1,5,6,2,3]
i
1
current
1
bar
0
left
-1
width
1
area
2
increasingIndices
[]
best
2
equalTransfer
false
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,1,5,6,2,3]
i
1
current
1
increasingIndices
[1]
best
2
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,1,5,6,2,3]
i
2
current
5
increasingIndices
[1]
best
2
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,1,5,6,2,3]
i
2
current
5
increasingIndices
[1,2]
best
2
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,1,5,6,2,3]
i
3
current
6
increasingIndices
[1,2]
best
2
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,1,5,6,2,3]
i
3
current
6
increasingIndices
[1,2,3]
best
2
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,1,5,6,2,3]
i
4
current
2
increasingIndices
[1,2,3]
best
2
Finalize a span at a genuinely smaller right boundary.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,1,5,6,2,3]
i
4
current
2
bar
3
left
2
width
1
area
6
increasingIndices
[1,2]
best
6
equalTransfer
false
Finalize a span at a genuinely smaller right boundary.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,1,5,6,2,3]
i
4
current
2
bar
2
left
1
width
2
area
10
increasingIndices
[1]
best
10
equalTransfer
false
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,1,5,6,2,3]
i
4
current
2
increasingIndices
[1,4]
best
10
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,1,5,6,2,3]
i
5
current
3
increasingIndices
[1,4]
best
10
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,1,5,6,2,3]
i
5
current
3
increasingIndices
[1,4,5]
best
10
Use a virtual lower sentinel to flush pending bars.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,1,5,6,2,3]
i
6
current
-1
increasingIndices
[1,4,5]
best
10
Finalize a span at a genuinely smaller right boundary.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,1,5,6,2,3]
i
6
current
-1
bar
5
left
4
width
1
area
3
increasingIndices
[1,4]
best
10
equalTransfer
false
Finalize a span at a genuinely smaller right boundary.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,1,5,6,2,3]
i
6
current
-1
bar
4
left
1
width
4
area
8
increasingIndices
[1]
best
10
equalTransfer
false
Finalize a span at a genuinely smaller right boundary.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,1,5,6,2,3]
i
6
current
-1
bar
1
left
-1
width
6
area
6
increasingIndices
[]
best
10
equalTransfer
false
Complete the flush without inserting a sentinel.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,1,5,6,2,3]
i
6
current
-1
increasingIndices
[]
best
10
Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
result
10

Equal bars transfer future width ownership

Input: [2,2,2] · Result: 6

Step 1 of 13: Start with no pending histogram spans.

Pending indices will have strictly increasing heights after each real insertion.

Original array positions

0: 2
1: 2
2: 2

Histogram bars and the current candidate span

Best area so far: 0.

Increasing-height candidates — bottom to top

Empty at this step.

State after this step
Variable	Value
values	`[2,2,2]`
increasingIndices	`[]`
best	`0`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 public final class Solution {
 3     private static void validate(int[] heights) {
 4         for (int height : heights) if (height < 0) throw new IllegalArgumentException("nonnegative heights required");
 5     }
 6     public static long largestRectangleArea(int[] heights) {
 7         validate(heights);
 8         ArrayDeque<Integer> increasing = new ArrayDeque<>();
 9         long best = 0;
10         for (int i = 0; i <= heights.length; i++) {
11             int current = i == heights.length ? -1 : heights[i];
12             while (!increasing.isEmpty() && heights[increasing.peek()] >= current) {
13                 int bar = increasing.pop();
14                 int left = increasing.isEmpty() ? -1 : increasing.peek();
15                 long area = (long) heights[bar] * (i - left - 1);
16                 best = Math.max(best, area);
17             }
18             if (i < heights.length) increasing.push(i);
19         }
20         return best;
21     }
22     public static long baseline(int[] heights) {
23         validate(heights);
24         long best = 0;
25         for (int left = 0; left < heights.length; left++) {
26             int minimum = Integer.MAX_VALUE;
27             for (int right = left; right < heights.length; right++) {
28                 minimum = Math.min(minimum, heights[right]);
29                 best = Math.max(best, (long) minimum * (right - left + 1));
30             }
31         }
32         return best;
33     }
34 }
35

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with no pending histogram spans.
Pending indices will have strictly increasing heights after each real insertion.
values
[2,2,2]
increasingIndices
[]
best
0
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,2,2]
i
0
current
2
increasingIndices
[]
best
0
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,2,2]
i
0
current
2
increasingIndices
[0]
best
0
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,2,2]
i
1
current
2
increasingIndices
[0]
best
0
Evaluate a valid partial span and transfer equal-height ownership.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,2,2]
i
1
current
2
bar
0
left
-1
width
1
area
2
increasingIndices
[]
best
2
equalTransfer
true
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,2,2]
i
1
current
2
increasingIndices
[1]
best
2
Read the next real bar.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,2,2]
i
2
current
2
increasingIndices
[1]
best
2
Evaluate a valid partial span and transfer equal-height ownership.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,2,2]
i
2
current
2
bar
1
left
-1
width
2
area
4
increasingIndices
[]
best
4
equalTransfer
true
Push the new representative after all required pops.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,2,2]
i
2
current
2
increasingIndices
[2]
best
4
Use a virtual lower sentinel to flush pending bars.
The sentinel is a boundary event and is never read from the source or pushed.
values
[2,2,2]
i
3
current
-1
increasingIndices
[2]
best
4
Finalize a span at a genuinely smaller right boundary.
The candidate covers [left+1,i). Equal pops can extend later through the newer representative; a strict smaller boundary closes the span.
values
[2,2,2]
i
3
current
-1
bar
2
left
-1
width
3
area
6
increasingIndices
[]
best
6
equalTransfer
false
Complete the flush without inserting a sentinel.
Real stack heights are strictly increasing. Each real index is inserted once and removed at most once.
values
[2,2,2]
i
3
current
-1
increasingIndices
[]
best
6
Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
result
6

Test the contract

Input: []
Output: 0
No rectangle.
Input: [0,0]
Output: 0
Zero-height bars.
Input: [2,2,2]
Output: 6
Equal plateau handling.
Input: [2147483647,2147483647]
Output: 4294967294
Long area is required.

Common mistakes and counterexamples

Call every equal-height pop a maximal span

Counterexample: On [2,2], the first pop sees width one, while the true plateau width is two.

Explain ownership transfer and let the newer representative reach the later boundary.

Use width i-left

Counterexample: For one height-two bar at index zero, the empty left boundary is -1 and true width is one.

Subtract both excluded boundaries with i-left-1.

Read a physical sentinel outside the array

Counterexample: i=n is a boundary, not a valid bar index.

Select virtual -1 without reading heights[n], and do not push n.

Follow-ups

Use nearest-smaller arrays.

Compute strict-smaller boundaries on both sides and maximize height*(right-left-1). Prove a consistent duplicate policy or use genuinely strict-smaller boundaries for both passes; mixing tie rules can narrow or double-own spans incorrectly.

Return rectangle boundaries.

Save left+1, i, and the popped height whenever best improves. Define ties explicitly, and remember returned right is exclusive while source indices are inclusive positions.

Find a maximal rectangle in a binary matrix.

Treat each row as a histogram of consecutive ones above it, then run this algorithm per row. Validate a rectangular binary input and count O(RC) total time with O(C) histogram/stack state.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 145/20,000 characters

Self-review

I derive the exclusive width formula.I explain equal-height transfer instead of false maximality.I flush without indexing a sentinel bar.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Stacks: pending work, saved state, and monotonic spans

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.