Difficulty: HardStack

Largest Rectangle in Histogram

Problem in Plain English

Given the bar heights of a histogram where each bar is one unit wide, find the area of the largest rectangle that fits under consecutive bars. A nondecreasing stack reuses span boundaries to find the answer in linear time.

Problem Statement

Given an array of integers heights representing the histogram bar heights where the width of each bar is 1, return the area of the largest rectangle in the histogram.

For a bar of height h, the tallest rectangle using that height stretches left and right until a shorter bar blocks it, so its area is h times that span width. The answer is the maximum of this value over every bar.

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

Examples

Example 1

Input: heights = [2,1,5,6,2,3]
Output: 10

The bars of height 5 and 6 form a 5 by 2 rectangle of area 10, which beats every other span.

Example 2

Input: heights = [2,4]
Output: 4

The single bar of height 4 gives area 4, which is the largest achievable.

Example 3

Input: heights = [0]
Output: 0

There is one bar but its height is zero, so every rectangle has area zero. This checks both the minimum length and a zero height.

Example 4

Input: heights = [2,2,2]
Output: 6

Equal heights can share one rectangle: height 2 across all three bars gives area 6. Treating equality as a blocking shorter bar would miss this width.

Example 5

Input: heights = [2,0,2]
Output: 2

The zero splits the two positive bars. Any rectangle crossing it has height zero; either single height-2 bar gives the best area 2.

Intuition

A rectangle must cover consecutive bars, and its height cannot exceed the shortest bar it covers. In [2,1,5,6,2,3], bars at indices 2 and 3 have heights 5 and 6, so together they support height 5, width 2, and area 10. Extending that rectangle to index 4 lowers its allowed height to 2. Instead of repeatedly searching for these stopping points, a monotonic stack stores unfinished spans in nondecreasing height order: taller spans end when a shorter bar arrives.

Approaches

Expand Every Bar

Solution Details

Reveal Expand Every Bar: intuition, complexity, and code

Intuition

Fix one bar as the height of a rectangle, then walk left and right while all bars are at least that tall. The widest allowed span is the best rectangle at that height because heights are nonnegative. Repeating those walks for every bar is simple, but equal-height runs make it scan the same neighbours many times.

Step-by-Step Logic

Set maxArea = 0 and n = heights.length. For each index i, set currentHeight = heights[i] and both boundary pointers to i.
Move left backward while it is in bounds and its bar is at least currentHeight. Move right forward under the same condition. Both pointers finish outside the valid span, at shorter bars or beyond the array.
Compute width = right - left - 1 and update maxArea with currentHeight * width. In Example 1, index 0 stops at left = -1, right = 1, giving area 2.
Repeat for every bar. Index 1 spans all six bars for area 6; index 2 stops at 1 and 4, so height 5 across indices 2..3 gives area 10.
The remaining indices give areas 6, 8, and 3. Return maxArea = 10 after checking all six choices.

Why It Works

For each chosen height, the two walks include exactly the consecutive bars that can support it; a shorter bar cannot belong to that rectangle. Thus each measured area fits in the histogram. Any optimal rectangle has a shortest bar. When that bar is chosen, the algorithm can extend at least as far as the optimal rectangle, with the same height, and therefore finds an area at least as large. Since all measured areas are valid, taking their maximum gives exactly the optimum.

Dry Run

Expand Every Bar: variable states at each step
`i` / action	`currentHeight`	Every `left` value	Every `right` value	`width`	Area	`maxArea` before -> after
Initialize `n = 6`	-	-	-	-	-	`0`
`0`	`2`	`0 -> -1`	`0 -> 1`	`1 - (-1) - 1 = 1`	`2`	`0 -> 2`
`1`	`1`	`1 -> 0 -> -1`	`1 -> 2 -> 3 -> 4 -> 5 -> 6`	`6 - (-1) - 1 = 6`	`6`	`2 -> 6`
`2`	`5`	`2 -> 1`	`2 -> 3 -> 4`	`4 - 1 - 1 = 2`	`10`	`6 -> 10`
`3`	`6`	`3 -> 2`	`3 -> 4`	`4 - 2 - 1 = 1`	`6`	`10 -> 10`
`4`	`2`	`4 -> 3 -> 2 -> 1`	`4 -> 5 -> 6`	`6 - 1 - 1 = 4`	`8`	`10 -> 10`
`5`	`3`	`5 -> 4`	`5 -> 6`	`6 - 4 - 1 = 1`	`3`	`10 -> 10`
`i = 6`, loop ends	-	-	-	-	-	return `10`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Let n be the number of bars. Each bar starts two walks that together visit at most n + 1 positions; an all-equal input performs that work for all n bars, giving O(n^2) worst-case time. Only loop indices, boundary pointers, a height, a width, and the best area are stored: O(1) extra space, with no copied array. This baseline is too slow for n = 100000. The largest possible area is 100000 * 10000 = 1000000000, which fits Java int and is exact in JavaScript Number.

Code

Solution.java

1class Solution {2    public int largestRectangleArea(int[] heights) {3        int maxArea = 0;4        int n = heights.length;5        for (int i = 0; i < n; i++) {6            int currentHeight = heights[i];7            int left = i;8            int right = i;9            while (left >= 0 && heights[left] >= currentHeight) {10                left--;11            }12            while (right < n && heights[right] >= currentHeight) {13                right++;14            }15            int width = right - left - 1;16            maxArea = Math.max(maxArea, currentHeight * width);17        }18        return maxArea;19    }20}

Hints

Hint 1

The height of any rectangle is capped by its shortest bar, so think about which bars can serve as that minimum.

Hint 2

For each bar, the span it governs runs between the nearest shorter bar on the left and the nearest shorter bar on the right.

Hint 3

Keep a nondecreasing stack of start and height pairs and pop whenever a shorter bar ends the current spans. Carry each popped start forward before pushing the new height.

Edge Cases

Bars of height 0 contribute no area and force every taller bar on the stack to close.
Strictly increasing heights push every bar, so the whole answer comes from the final flush.
Strictly decreasing heights pop on every step, so each area is measured the moment its bar leaves the stack.
A single bar returns its own height as the whole answer.
Equal heights are not shorter boundaries: [2,2,2] returns 6; this code keeps duplicates until a smaller bar or the final flush.
Zeros split positive spans: [2,0,2] returns 2, while [0,0,0] returns 0.
At the largest bounds, 100000 bars of height 10000 return 1000000000; use the linear approach to handle that size.

Common Mistakes and Interview Tips

Returning early without flushing the bars left on the stack, which drops rectangles that reach the right edge.
Forgetting to carry the popped start index forward, which shrinks the width of the bar that replaces them.
Reading the popped pair in the wrong order and multiplying the stored index where the height belongs.
Adding one to i - index in the stack approach includes the shorter bar that just ended the span. In the expansion approach, use right - left - 1 because both stop pointers are excluded.
Sorting the heights destroys adjacency. Rectangles must cover consecutive bars in the original histogram.
Calling this stack strictly increasing when the code pops only on >: duplicates stay, so the invariant is nondecreasing heights.
Assuming the tallest individual bar is the answer: in Example 1, height 6 alone gives 6, while height 5 across two bars gives 10.

Key Takeaway

A monotonic stack turns nearest-smaller queries into a single pass: rising values wait on the stack and each arrival settles every taller value before it.