Largest Rectangle in Histogram (LC 84)

Pattern: Monotonic Increasing Stack (previous smaller + next smaller)
Difficulty: Hard
Key Concept: For each bar, the widest rectangle of that bar’s height is bounded by the first strictly smaller bar on each side. A monotonic increasing stack finds both boundaries in one pass.

Problem Statement

Given heights[] representing a histogram where each bar has width 1, return the area of the largest rectangle that fits inside the histogram.

Input: int[] heights, 1 <= n <= 10^5, 0 <= heights[i] <= 10^4
Output: int — maximum rectangle area

Example

heights = [2, 1, 5, 6, 2, 3]   →   10   (bars 5 and 6, height 5, width 2)

        6      ██
        5    ██▓▓          ▓▓ = the winning 5 × 2 = 10 rectangle
        4    ██▓▓
        3    ██▓▓    ██
        2  ██      ██▓▓
        1  ██  ██████
           0 1  2 3  4 5

1. Algorithm & Pseudocode

Brute force

best = 0
for i from 0 to n-1:
    minHeight = heights[i]
    for j from i to n-1:                  // every subarray [i..j]
        minHeight = min(minHeight, heights[j])
        best = max(best, minHeight * (j - i + 1))
return best

Optimal (monotonic increasing stack)

stack = empty stack of INDICES, heights increasing bottom→top
best = 0

for i from 0 to n:                        // note: n inclusive — sentinel step
    curHeight = (i == n) ? 0 : heights[i] // sentinel 0 drains the stack

    while stack not empty AND heights[stack.top] > curHeight:
        h = heights[stack.pop()]
        // left boundary is now the new top; right boundary is i
        width = stack.isEmpty() ? i : (i - stack.top - 1)
        best = max(best, h * width)

    stack.push(i)

return best

2. Step-by-Step Analysis (Beginner-Friendly)

Reframe the problem: fix the height, then maximise the width Any rectangle’s height equals the shortest bar it spans. So instead of enumerating rectangles, enumerate bars, and for each bar i ask: “if the rectangle’s height is exactly heights[i], how wide can it stretch?”
How far can it stretch? Left until you hit a bar shorter than heights[i]; right until you hit a bar shorter than heights[i]. Anything shorter would force the rectangle’s height down. So: width = nextSmallerIndex - prevSmallerIndex - 1.
The stack finds both boundaries at once Keep indices with increasing heights. When bar i is shorter than the stack top, it is the “next smaller” for that top — that’s the right boundary. And after popping, the new stack top is by construction the closest bar to the left that’s still shorter — the left boundary. One pop yields both.
Why stack.isEmpty() means width = i An empty stack means nothing to the left was ever shorter, so the rectangle extends all the way back to index 0 — width i - 0 = i.
The sentinel trick Running i up to n with a virtual height of 0 guarantees every remaining bar gets popped and measured. Without it you’d need a separate drain loop after the main loop — same logic written twice, and a classic place to introduce a bug.
Why O(n) Same amortisation as every monotonic stack: n+1 pushes, at most n+1 pops.

3. The Dry Run

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

i	cur	Pops: h, width, area	Stack after	best
0	2	—	`[0]`	0
1	1	pop 0: h=2, stack empty → w=1, area=2	`[1]`	2
2	5	— (5 > 1)	`[1,2]`	2
3	6	— (6 > 5)	`[1,2,3]`	2
4	2	pop 3: h=6, w=4−2−1=1, area=6 pop 2: h=5, w=4−1−1=2, area=10	`[1,4]`	10
5	3	— (3 > 2)	`[1,4,5]`	10
6	0 (sentinel)	pop 5: h=3, w=6−4−1=1, area=3 pop 4: h=2, w=6−1−1=4, area=8 pop 1: h=1, stack empty → w=6, area=6	`[6]`	10

Answer: 10 ✓ (the 5-and-6 pair: height 5, width 2)

4. Java Solution

Brute Force

class Solution {
    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]);   // height of span [i..j]
                best = Math.max(best, minHeight * (j - i + 1));
            }
        }
        return best;
    }
}

Time O(n²) · Space O(1) — TLE at n = 10^5

Optimal

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

        for (int i = 0; i <= n; i++) {              // i == n is the sentinel step
            int cur = (i == n) ? 0 : heights[i];    // virtual 0-height bar drains the stack

            while (!stack.isEmpty() && heights[stack.peek()] > cur) {
                int h = heights[stack.pop()];
                // right boundary = i; left boundary = new stack top (or -1 if empty)
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                best = Math.max(best, h * width);
            }
            stack.push(i);
        }
        return best;
    }
}

Time O(n) · Space O(n)

Overflow note: with n = 10^5 and heights[i] = 10^4, max area is 10^9 — that fits in int (max ≈ 2.1·10^9). If the constraints were larger, long would be required. Mention that you checked.

5. The “Java vs. Others” Edge

ArrayDeque over Stack — the usual reason (synchronized Vector, wrong iteration order), plus ArrayDeque is array-backed so it’s cache-friendly for the tight pop loop here.
heights[stack.peek()] — the auto-unboxing happens at the array index. Guard with !stack.isEmpty() first; peek() returns null on empty and unboxing it throws NPE.
Sentinel via (i == n) ? 0 : heights[i] instead of Arrays.copyOf(heights, n + 1) — avoids allocating and copying a 10^5 array just to append one zero.
Math.max / Math.min compile to intrinsics on HotSpot (branchless on most CPUs), so there’s no reason to hand-roll comparisons.

6. Complexity Summary

Approach	Time	Space	Notes
Brute force (all spans)	O(n²)	O(1)	Recomputes minimum for every span
Divide & conquer (segment tree min)	O(n log n)	O(n)	Degrades to O(n²) on sorted input without a segment tree
Monotonic stack	O(n)	O(n)	Each index pushed once, popped once

#	Problem	Connection
LC 85	Maximal Rectangle	Run LC 84 once per matrix row over a running `heights[]`
LC 42	Trapping Rain Water	Same stack shape, but accumulates gaps instead of areas
LC 907	Sum of Subarray Minimums	prev-smaller / next-smaller contribution counting
LC 1856	Maximum Subarray Min-Product	LC 84’s boundaries + prefix sums