LeetCode 84: Largest Rectangle in Histogram

Problem Restatement

We are given an integer array heights.

Each value represents the height of one bar in a histogram.

Each bar has width 1.

We need to return the area of the largest rectangle that can be formed inside the histogram.

The rectangle must use consecutive bars. Its height is limited by the shortest bar in that chosen range.

The official statement gives heights = [2, 1, 5, 6, 2, 3] with output 10, and heights = [2, 4] with output 4. The constraints are 1 <= heights.length <= 10^5 and 0 <= heights[i] <= 10^4.

Input and Output

Function shape:

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        ...

Examples

Example 1:

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

The largest rectangle uses the bars:

[5, 6]

The limiting height is 5.

The width is 2.

So the area is:

5 * 2 = 10

Answer:

10

Example 2:

heights = [2, 4]

Possible best rectangles:

height 4, width 1 => area 4
height 2, width 2 => area 4

Answer:

4

Example 3:

heights = [2, 1, 2]

The best rectangle uses all three bars with height 1.

Area:

1 * 3 = 3

Answer:

3

First Thought: Try Every Range

A rectangle is defined by a left boundary and a right boundary.

For every pair:

left <= right

we can compute:

height = min(heights[left:right + 1])
width = right - left + 1
area = height * width

Then take the maximum area.

Code shape:

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        best = 0
        n = len(heights)

        for left in range(n):
            min_height = float("inf")

            for right in range(left, n):
                min_height = min(min_height, heights[right])
                width = right - left + 1
                best = max(best, min_height * width)

        return best

This avoids recomputing the minimum from scratch, but it still checks all ranges.

Problem With Brute Force

There are O(n^2) contiguous ranges.

Since n can be 10^5, this is too slow.

We need to avoid trying every possible rectangle.

Key Insight

Instead of asking:

“What is the best rectangle for every range?”

ask:

“What is the widest rectangle where this bar is the shortest bar?”

For a bar at index i with height heights[i], it can extend left and right until it hits a bar shorter than itself.

So we need to know:

If those boundaries are known, then the widest rectangle using heights[i] as the limiting height is:

width = right_smaller_index - left_smaller_index - 1
area = heights[i] * width

A monotonic increasing stack finds these boundaries efficiently.

Monotonic Stack Idea

The stack stores indices.

The heights at those indices are increasing from bottom to top.

stack = []

When we see a new bar shorter than the bar at the top of the stack, that means the current bar is the first smaller bar to the right for the popped bar.

So we can compute the popped bar’s final rectangle immediately.

For a popped index top:

height = heights[top]

The current index i is the first smaller index on the right.

After popping, the new stack top is the previous smaller index on the left.

So:

right = i
left = stack[-1] if stack else -1
width = right - left - 1
area = height * width

Sentinel Trick

At the end of the array, some bars may still be inside the stack.

Those bars never found a smaller bar on the right.

We can force them to be processed by appending a sentinel height:

0

This final 0 is smaller than all positive bars and no larger than any valid height, so it flushes the stack.

To avoid mutating the input, we can loop over:

heights + [0]

Algorithm

Set:

stack = []
best = 0

Loop through every index and height in heights + [0].

For each bar:

1. While the stack is non-empty and the current height is smaller than the height at the stack top, pop the stack.
2. Use the popped height as the rectangle height.
3. The current index is the right boundary.
4. The new stack top is the left boundary.
5. Compute the area and update best.
6. Push the current index.

At the end, return best.

Walkthrough

Use:

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

We process:

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

At index 0, height 2.

Stack is empty, so push:

stack = [0]

At index 1, height 1.

Height 1 is smaller than 2, so pop index 0.

height = 2
right = 1
left = -1
width = 1 - (-1) - 1 = 1
area = 2

Push index 1.

stack = [1]

At index 2, height 5.

Height 5 is greater than 1, so push.

stack = [1, 2]

At index 3, height 6.

Height 6 is greater than 5, so push.

stack = [1, 2, 3]

At index 4, height 2.

Height 2 is smaller than 6, so pop index 3.

height = 6
right = 4
left = 2
width = 4 - 2 - 1 = 1
area = 6

Height 2 is also smaller than 5, so pop index 2.

height = 5
right = 4
left = 1
width = 4 - 1 - 1 = 2
area = 10

Now best = 10.

Push index 4.

At the end, the sentinel 0 pops all remaining bars.

The maximum area remains:

10

Correctness

Every rectangle has a shortest bar. Choose one shortest bar inside that rectangle.

When the algorithm pops a bar at index i, it has just found the first bar to the right that is shorter than heights[i].

After popping, the new stack top is the nearest bar to the left that is shorter than heights[i]. If the stack is empty, no such left bar exists.

Therefore, at the moment index i is popped, the algorithm knows the widest possible range where heights[i] can be the limiting height.

The computed width:

right - left - 1

covers exactly the bars between the nearest smaller bars.

No wider rectangle with height heights[i] is possible, because extending one more step left or right would hit a shorter bar.

The algorithm computes this widest rectangle once for every bar, either when a smaller bar appears or when the sentinel is processed.

Since every possible maximum rectangle has some limiting bar, and the algorithm checks the widest rectangle for every limiting bar, the maximum recorded area is the answer.

Complexity

Let:

n = len(heights)

Implementation

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

        for i, h in enumerate(heights + [0]):
            while stack and h < heights[stack[-1]]:
                height = heights[stack.pop()]
                left = stack[-1] if stack else -1
                width = i - left - 1
                best = max(best, height * width)

            stack.append(i)

        return best

Code Explanation

The stack stores indices, not heights:

stack = []

This lets us compute widths from positions.

We scan all bars plus a sentinel:

for i, h in enumerate(heights + [0]):

When the current height is smaller than the height at the stack top:

while stack and h < heights[stack[-1]]:

the top bar can no longer extend to the right.

So we pop it:

height = heights[stack.pop()]

After popping, the new stack top is the previous smaller bar:

left = stack[-1] if stack else -1

The current index i is the next smaller bar.

So the valid width is:

width = i - left - 1

Then update the best area:

best = max(best, height * width)

Finally, push the current index:

stack.append(i)

The sentinel index is pushed at the end, but that does not matter because the loop finishes immediately after.

Testing

def run_tests():
    s = Solution()

    assert s.largestRectangleArea([2, 1, 5, 6, 2, 3]) == 10
    assert s.largestRectangleArea([2, 4]) == 4
    assert s.largestRectangleArea([2, 1, 2]) == 3
    assert s.largestRectangleArea([1, 2, 3, 4, 5]) == 9
    assert s.largestRectangleArea([5, 4, 3, 2, 1]) == 9
    assert s.largestRectangleArea([0]) == 0
    assert s.largestRectangleArea([4]) == 4
    assert s.largestRectangleArea([2, 2, 2]) == 6

    print("all tests passed")

run_tests()

Test meaning: