Largest Rectangle Histogram LeetCode 84

LeetCode 84 — Largest Rectangle in Histogram — gives you an array of non-negative integers where each element represents the height of a bar with unit width. The bars are placed side by side forming a histogram, and your task is to find the area of the largest rectangle that can be formed within the histogram boundaries. A rectangle must be axis-aligned and cannot exceed the height of any bar it spans.

The key constraint is that a rectangle spanning bars from index i to index j can only be as tall as the minimum bar height in that range — otherwise the rectangle would protrude above one of the bars. This means you are searching for the best trade-off between height and width: a taller rectangle covers fewer bars, while a wider rectangle is limited by the shortest bar in its span.

With up to 100,000 bars in the input, a naive O(n^2) approach that checks every pair of left and right boundaries will time out. The optimal solution processes each bar exactly twice (once pushed, once popped) using a monotonic stack, achieving O(n) time and O(n) space. Understanding why a monotonic stack enables this is the core insight of the problem.

The brute-force solution iterates over every possible bar as the height-limiting bar. For each bar at index i, it expands left and right as long as neighboring bars are at least as tall. The width of the rectangle is the total span covered, and the area is heights[i] times that width. Tracking the maximum area across all bars gives the answer.

In code: for each i in range(n), set left = i and right = i. While left > 0 and heights[left-1] >= heights[i]: left -= 1. While right < n-1 and heights[right+1] >= heights[i]: right += 1. area = heights[i] * (right - left + 1). Update max_area. This is straightforward to implement and easy to reason about, but the nested expansion makes it O(n^2) in the worst case — a flat histogram causes each bar to expand across all others.

The brute-force correctly identifies the limiting bar for every possible rectangle, but it redundantly recomputes boundaries for overlapping ranges. The monotonic stack eliminates this redundancy by computing the left and right boundaries for every bar in a single coordinated pass rather than expanding independently from each bar.

A monotonic increasing stack stores indices of bars in increasing order of height from bottom to top. The invariant is that the bar at any stack position is shorter than or equal to every bar above it. This invariant encodes left-boundary information: every bar currently in the stack has already survived being the minimum height for all bars pushed after it, so the bar beneath it in the stack is the nearest bar to its left that is strictly shorter.

When we encounter a new bar at index i with height less than the bar at the stack top (index j), we know that bar j cannot extend any further to the right — the new shorter bar caps it. This is the right boundary. We pop bar j, compute its area using the current index i as the right boundary and the new stack top as the left boundary, and repeat while the stack top is still taller than the current bar. This ensures every bar is processed at most once.

The stack effectively defers area calculation until each bar finds its right boundary. Bars are pushed in order and popped in reverse order (LIFO), and each pop triggers a complete area computation for the popped bar. Because each bar is pushed once and popped once, the algorithm is O(n) overall despite the nested while loop.

When bar j is popped from the stack during processing of index i, we know: the right boundary is i (the first bar to the right shorter than heights[j]), and the left boundary is the new stack top after the pop (the first bar to the left shorter than heights[j]). Every bar between these two boundaries is at least as tall as heights[j], so a rectangle of height heights[j] fits across that entire span.

Concretely: height = heights[j]. If the stack is non-empty after the pop, let left = stack[-1] (the new top). The width is i - left - 1, because the rectangle spans from left+1 to i-1 inclusive. If the stack is empty after the pop, there is no shorter bar to the left — the rectangle extends all the way to index 0, so width = i. Area = height * width.

This formula accounts for all the bars between the new stack top and the current index i that have heights >= heights[j]. Those bars were previously pushed onto the stack and will be popped in later iterations (or have already been popped), but for the purpose of bar j's rectangle, they are included in the width because they are all tall enough. The width formula is the key algorithmic insight: it measures the gap between the two nearest shorter bars on each side.

After scanning all bars in the array, some bars may remain on the stack. These are bars that never found a shorter bar to their right — meaning they extend all the way to the right end of the histogram. They must be processed to ensure no valid rectangle is missed.

For each remaining bar j popped from the stack using n (the array length) as the right boundary: width = n - stack[-1] - 1 if stack non-empty, else n. Area = heights[j] * width. This is identical to the main loop formula with i replaced by n. The same stack-top logic applies: the new stack top after each pop is the nearest shorter bar to the left.

The cleanest way to handle this post-loop processing is to append a sentinel bar with height 0 before the main loop. The sentinel guarantees that every real bar will eventually find a shorter right boundary during the main loop, eliminating the need for any post-loop code. This is a standard trick that simplifies the implementation without affecting correctness.

Python solution: def largestRectangleArea(heights): heights.append(0); stack = []; max_area = 0; for i, h in enumerate(heights): while stack and heights[stack[-1]] > h: j = stack.pop(); width = i - stack[-1] - 1 if stack else i; max_area = max(max_area, heights[j] * width); stack.append(i); return max_area. The sentinel 0 is appended in-place. The enumerate gives both index and height. The single loop handles all pops and pushes in O(n). Total time O(n), space O(n) for the stack.

Trace through [2,1,5,6,2,3]: push 0(h=2). i=1,h=1: pop 0, width=1, area=2. push 1. i=2,h=5: push 2. i=3,h=6: push 3. i=4,h=2: pop 3(h=6), width=4-2-1=1, area=6. Pop 2(h=5), width=4-1-1=2, area=10. Push 4. i=5,h=3: push 5. i=6,h=0(sentinel): pop 5(h=3), width=6-4-1=1, area=3. Pop 4(h=2), width=6-1-1=4, area=8. Pop 1(h=1), width=6, area=6. Max = 10.

Java solution: public int largestRectangleArea(int[] heights) { int n = heights.length; int[] h = Arrays.copyOf(heights, n+1); // sentinel 0 already default; Deque<Integer> stack = new ArrayDeque<>(); int max = 0; for (int i = 0; i <= n; i++) { while (!stack.isEmpty() && h[stack.peek()] > h[i]) { int j = stack.pop(); int width = stack.isEmpty() ? i : i - stack.peek() - 1; max = Math.max(max, h[j] * width); } stack.push(i); } return max; }. Arrays.copyOf pads with 0 — the sentinel is the last element. The Deque is used as a stack via push/pop/peek.

Maximal Rectangle (LeetCode 85) extends Largest Rectangle in Histogram to a 2D binary matrix. For each row, build a histogram of consecutive 1s above that row, then apply the exact same LeetCode 84 monotonic stack algorithm to find the largest rectangle in that row's histogram. The total time complexity is O(m*n) where m and n are the matrix dimensions — essentially running LeetCode 84 once per row.

Trapping Rain Water (LeetCode 42) also uses a monotonic stack to compute bounded areas efficiently. Instead of finding the maximum rectangle, it finds the water trapped between taller bars on both sides of each bar. The stack-based approach for Trapping Rain Water processes bars layer by layer, and the width calculation uses a very similar "gap between two bounding bars" formula as Largest Rectangle in Histogram.

Daily Temperatures (LeetCode 739) and Next Greater Element (LeetCode 496) are the introductory monotonic stack problems — they use a decreasing stack to find the next greater element for each position. These are good starting points before tackling the more complex area calculations in LeetCode 84 and 85. Together, these problems form the core monotonic stack family that appears frequently in coding interviews.