LeetCode Problem 84

Difficulty: 🔴 Hard
Topics: Array, Stack, Monotonic Stack

Solution

LeetCode 84 - Largest Rectangle in Histogram

Problem Understanding

This problem asks us to find the largest rectangular area that can be formed inside a histogram. A histogram is represented as an array of integers called heights, where each integer describes the height of a bar, and every bar has a width of exactly 1.

The goal is to determine the maximum possible area of any rectangle that can be formed using one or more adjacent bars. A rectangle does not need to span the entire histogram. Instead, it can extend across any continuous range of bars, but its height is limited by the shortest bar within that range.

For example, if we have:

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

We might consider the bars [5,6]. Since the shortest height in that segment is 5, we can create a rectangle of height 5 and width 2, producing an area of:

5 × 2 = 10

This turns out to be the largest rectangle in the histogram.

The input is an integer array where:

• heights[i] represents the height of the i-th bar.
• Every bar has width 1.
• Bars are placed next to each other with no gaps.

The expected output is a single integer representing the maximum rectangle area possible.

The constraints are important:

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

The array size can be as large as 100,000, which immediately tells us that expensive nested-loop approaches may be too slow. An O(n²) or O(n³) solution risks timing out on large inputs. This strongly suggests that we need a linear or near-linear solution.

Several edge cases can trip up naive implementations. Histograms with increasing heights, decreasing heights, or repeated equal heights behave differently and often reveal logical mistakes. Arrays containing zeros are also important because a height of 0 effectively breaks a rectangle. A histogram with only one bar is another special case where the answer is simply that bar’s height.

The problem guarantees that the input array is non-empty and contains non-negative integers, so we never need to handle invalid input or negative heights.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to examine every possible contiguous subarray of bars.

For each starting index, we can expand toward the right while keeping track of the minimum height encountered so far. Since the rectangle height is limited by the smallest bar in the range, the area for every segment becomes:

minimum height × width

We compute this for all possible ranges and track the maximum area.

This approach works because it explicitly checks every valid rectangle. Since every possible contiguous region is evaluated, the maximum area found must be correct.

However, it is too slow for the given constraints. There are O(n²) possible intervals, and while we can optimize minimum tracking to avoid recomputation, the overall complexity still becomes O(n²). With n = 100,000, this is impractical.

Optimal Approach, Monotonic Increasing Stack

The key insight is that for every bar, we want to determine:

• How far it can extend to the left
• How far it can extend to the right

before encountering a shorter bar.

If we know these boundaries, we can calculate the maximum rectangle where this bar is the limiting height.

For a bar at index i:

area = height[i] × width

where:

width = right_boundary - left_boundary - 1

Instead of explicitly searching left and right for every bar, which would be expensive, we use a monotonic increasing stack.

The stack stores indices of bars in increasing height order. Whenever we encounter a shorter bar, we know that the taller bars on the stack cannot extend further. This gives us enough information to compute their maximum rectangle immediately.

This is efficient because every element is pushed and popped at most once, giving an O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every contiguous range and compute rectangle areas
Optimal	O(n)	O(n)	Monotonic increasing stack processes each bar once

Algorithm Walkthrough

Optimal Algorithm Using a Monotonic Stack

1. Initialize an empty stack and a variable max_area = 0.

The stack will store indices of histogram bars in increasing order of height. We store indices instead of values because we need positions to calculate widths later. 2. Iterate through all bars in the histogram.

For each bar, compare its height with the bar at the top of the stack. 3. Maintain the increasing property of the stack.

If the current bar is taller than or equal to the top of the stack, push its index onto the stack.

This preserves the increasing height order. 4. When a shorter bar appears, pop taller bars.

If the current height is smaller than the height of the bar on top of the stack, we know that the taller bar cannot continue beyond this point.

We repeatedly pop from the stack and calculate areas. 5. Calculate the rectangle for the popped bar.

After popping:

• The current index gives the right boundary.
• The new top of the stack gives the left boundary.
• If the stack becomes empty, the rectangle extends to the beginning.

The width becomes:

width = current_index - stack[-1] - 1

or:

width = current_index

if the stack is empty.

Then calculate:

area = popped_height × width

Update max_area. 6. Continue processing until all bars are examined. 7. Add a sentinel value.

To ensure all remaining bars are processed, append a virtual height 0 at the end. This forces the stack to empty naturally. 8. Return max_area.

Why it works

The key invariant is that the stack always contains indices of bars in increasing height order. When a shorter bar appears, we immediately know the right boundary for every taller bar that must be removed. Since the stack also preserves information about previous smaller elements, we automatically know the left boundary as well.

Every bar is processed exactly once as a potential limiting height for a rectangle, guaranteeing that the maximum rectangle is never missed.

Python Solution

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        max_area = 0

        # Add sentinel height to process remaining bars
        heights.append(0)

        for index, height in enumerate(heights):
            while stack and heights[stack[-1]] > height:
                top_index = stack.pop()
                current_height = heights[top_index]

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

                area = current_height * width
                max_area = max(max_area, area)

            stack.append(index)

        return max_area

The implementation starts by initializing an empty stack and a variable to track the maximum area.

A sentinel value 0 is appended to the array. This is an elegant trick that ensures all remaining bars in the stack are processed at the end without requiring separate cleanup logic.

During iteration, the stack maintains increasing heights. Whenever the current bar is shorter than the top of the stack, we repeatedly pop taller bars because they can no longer extend further.

For each popped bar, the current index acts as the right boundary. The new top of the stack gives the left boundary. This allows us to calculate the width and therefore the area.

After processing necessary pops, the current index is added to the stack so the increasing order property remains intact.

Finally, the maximum rectangle area is returned.

Go Solution

func largestRectangleArea(heights []int) int {
	stack := []int{}
	maxArea := 0

	// Add sentinel value
	heights = append(heights, 0)

	for i, height := range heights {
		for len(stack) > 0 && heights[stack[len(stack)-1]] > height {
			topIndex := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			currentHeight := heights[topIndex]

			var width int
			if len(stack) > 0 {
				width = i - stack[len(stack)-1] - 1
			} else {
				width = i
			}

			area := currentHeight * width
			if area > maxArea {
				maxArea = area
			}
		}

		stack = append(stack, i)
	}

	return maxArea
}

The Go implementation follows exactly the same logic as the Python version. The primary difference is stack handling. In Go, slices are used as stacks, with append() for push operations and slicing for pops.

Go does not have Python's built-in max() function, so maximum area updates are performed with an explicit comparison.

There are no special concerns about integer overflow because the maximum possible rectangle area is:

10^5 × 10^4 = 10^9

which fits comfortably inside Go's int type.

Worked Examples

Example 1

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

After appending sentinel:

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

Index	Height	Stack Before	Action	Area Calculated	Max Area
0	2	[]	Push 0	-	0
1	1	[0]	Pop 2	2 × 1 = 2	2
1	1	[]	Push 1	-	2
2	5	[1]	Push 2	-	2
3	6	[1,2]	Push 3	-	2
4	2	[1,2,3]	Pop 6	6 × 1 = 6	6
4	2	[1,2]	Pop 5	5 × 2 = 10	10
4	2	[1]	Push 4	-	10
5	3	[1,4]	Push 5	-	10
6	0	[1,4,5]	Pop 3	3 × 1 = 3	10
6	0	[1,4]	Pop 2	2 × 4 = 8	10
6	0	[1]	Pop 1	1 × 6 = 6	10

Final answer:

10

The largest rectangle comes from bars [5,6], where height 5 spans width 2.

Example 2

heights = [2,4]

After appending sentinel:

[2,4,0]

Index	Height	Stack Before	Action	Area Calculated	Max Area
0	2	[]	Push 0	-	0
1	4	[0]	Push 1	-	0
2	0	[0,1]	Pop 4	4 × 1 = 4	4
2	0	[0]	Pop 2	2 × 2 = 4	4

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every bar is pushed and popped at most once
Space	O(n)	The stack may store all indices in the worst case

The linear time complexity comes from the fact that each element enters and leaves the stack only once. Even though there is a nested while loop, the total number of pop operations across the entire execution is bounded by n.

The space complexity is O(n) because, in the worst case of strictly increasing heights, all indices remain in the stack simultaneously.

Test Cases

solution = Solution()

assert solution.largestRectangleArea([2, 1, 5, 6, 2, 3]) == 10  # Example 1
assert solution.largestRectangleArea([2, 4]) == 4  # Example 2

assert solution.largestRectangleArea([5]) == 5  # Single bar
assert solution.largestRectangleArea([0]) == 0  # Single zero

assert solution.largestRectangleArea([1, 2, 3, 4, 5]) == 9  # Increasing heights
assert solution.largestRectangleArea([5, 4, 3, 2, 1]) == 9  # Decreasing heights

assert solution.largestRectangleArea([2, 2, 2, 2]) == 8  # All equal heights
assert solution.largestRectangleArea([0, 0, 0]) == 0  # All zeros

assert solution.largestRectangleArea([2, 1, 2]) == 3  # Valley shape
assert solution.largestRectangleArea([4, 2, 0, 3, 2, 5]) == 6  # Mixed heights

assert solution.largestRectangleArea([10000] * 100000) == 1000000000  # Stress test

Test	Why
[2,1,5,6,2,3]	Verifies the primary example
[2,4]	Verifies small input
[5]	Single-element histogram
[0]	Minimum possible height
[1,2,3,4,5]	Increasing sequence stresses stack growth
[5,4,3,2,1]	Decreasing sequence stresses repeated popping
[2,2,2,2]	Equal heights test width expansion
[0,0,0]	All bars have zero height
[2,1,2]	Valley shape tests boundary logic
[4,2,0,3,2,5]	Mixed pattern with reset points
[10000] * 100000	Maximum-size stress case

Edge Cases

Single Bar Histogram

A histogram containing only one bar, such as:

[5]

can be easy to mishandle if the implementation assumes multiple boundaries exist. Since there is only one possible rectangle, the answer is simply the height itself. The algorithm handles this naturally because the sentinel value forces the single bar to be popped and evaluated.

Strictly Increasing Heights

An input like:

[1,2,3,4,5]

is tricky because no rectangle gets computed during the main iteration. Every bar is simply pushed onto the stack. Without proper cleanup, the algorithm would miss the answer entirely.

The sentinel 0 solves this issue by triggering pops for all remaining bars at the end.

Strictly Decreasing Heights

For input:

[5,4,3,2,1]

every new bar causes immediate popping. This can expose bugs in width calculation because boundaries change rapidly.

The implementation correctly computes widths by using the new top of the stack after each pop. This guarantees the left boundary is always accurate.

Histograms with Zero Heights

An input like:

[2,0,2]

contains a zero-height bar that effectively splits the histogram into separate sections.

The algorithm handles this naturally because a height of 0 forces all taller bars to be popped, preventing rectangles from incorrectly spanning across the zero.