# 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

| Item | Meaning |
|---|---|
| Input | An integer array `heights` |
| Output | Maximum rectangle area |
| Bar width | Every bar has width `1` |
| Rectangle rule | It must cover consecutive bars |
| Height rule | The rectangle height is the minimum bar height inside that range |

Function shape:

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

## Examples

Example 1:

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

The largest rectangle uses the bars:

```python
[5, 6]
```

The limiting height is `5`.

The width is `2`.

So the area is:

```python
5 * 2 = 10
```

Answer:

```python
10
```

Example 2:

```python
heights = [2, 4]
```

Possible best rectangles:

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

Answer:

```python
4
```

Example 3:

```python
heights = [2, 1, 2]
```

The best rectangle uses all three bars with height `1`.

Area:

```python
1 * 3 = 3
```

Answer:

```python
3
```

## First Thought: Try Every Range

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

For every pair:

```python
left <= right
```

we can compute:

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

Then take the maximum area.

Code shape:

```python
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:

| Boundary | Meaning |
|---|---|
| Previous smaller bar | First bar to the left with height `< heights[i]` |
| Next smaller bar | First bar to the right with height `< heights[i]` |

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

```python
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.

```python
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`:

```python
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:

```python
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:

```python
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:

```python
heights + [0]
```

## Algorithm

Set:

```python
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:

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

We process:

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

At index `0`, height `2`.

Stack is empty, so push:

```python
stack = [0]
```

At index `1`, height `1`.

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

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

Push index `1`.

```python
stack = [1]
```

At index `2`, height `5`.

Height `5` is greater than `1`, so push.

```python
stack = [1, 2]
```

At index `3`, height `6`.

Height `6` is greater than `5`, so push.

```python
stack = [1, 2, 3]
```

At index `4`, height `2`.

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

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

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

```python
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:

```python
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:

```python
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:

```python
n = len(heights)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each index is pushed once and popped once |
| Space | `O(n)` | The stack may hold up to `n` indices |

## Implementation

```python
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:

```python
stack = []
```

This lets us compute widths from positions.

We scan all bars plus a sentinel:

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

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

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

the top bar can no longer extend to the right.

So we pop it:

```python
height = heights[stack.pop()]
```

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

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

The current index `i` is the next smaller bar.

So the valid width is:

```python
width = i - left - 1
```

Then update the best area:

```python
best = max(best, height * width)
```

Finally, push the current index:

```python
stack.append(i)
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| `[2, 1, 5, 6, 2, 3]` | Main example |
| `[2, 4]` | Small official example |
| `[2, 1, 2]` | Best rectangle spans all bars |
| Increasing heights | Checks final sentinel flush |
| Decreasing heights | Checks repeated popping |
| `[0]` | Zero-height bar |
| Single bar | Minimum non-empty input |
| Equal heights | Width expansion across equal bars |