# LeetCode 85: Maximal Rectangle

## Problem Restatement

We are given a binary matrix filled with characters:

```python
"0"
"1"
```

We need to find the largest rectangle that contains only `"1"` cells and return its area.

The rectangle must be axis-aligned. That means its sides follow the matrix rows and columns.

The official problem states: given a `rows x cols` binary matrix filled with `0`s and `1`s, find the largest rectangle containing only `1`s and return its area. Example 1 uses `matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]` and returns `6`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A binary matrix `matrix` of `"0"` and `"1"` characters |
| Output | Area of the largest rectangle containing only `"1"` |
| Rectangle rule | The rectangle must use contiguous rows and contiguous columns |
| Cell rule | Every cell inside the rectangle must be `"1"` |

Function shape:

```python
class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        ...
```

## Examples

Example 1:

```python
matrix = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"],
]
```

The largest rectangle has area:

```python
6
```

One such rectangle uses rows `1` to `2` and columns `2` to `4`:

```python
1 1 1
1 1 1
```

Answer:

```python
6
```

Example 2:

```python
matrix = [["0"]]
```

There is no rectangle of `1`s.

Answer:

```python
0
```

Example 3:

```python
matrix = [["1"]]
```

The single cell itself is the largest rectangle.

Answer:

```python
1
```

## First Thought: Try Every Rectangle

A rectangle can be described by four boundaries:

```python
top
bottom
left
right
```

We could try every possible rectangle and check whether all cells inside it are `"1"`.

That is correct, but too slow.

For a matrix with `R` rows and `C` columns, there are many choices:

```python
O(R^2 * C^2)
```

rectangles.

Checking each rectangle cell by cell makes it even slower.

We need to reuse work.

## Key Insight

Each row can be treated as the bottom of a histogram.

For every column, count how many consecutive `"1"` cells appear above the current row, including the current row.

For example, after processing this row:

```python
["1", "1", "1", "1", "1"]
```

inside the matrix:

```python
[
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
]
```

the heights are:

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

because:

| Column | Consecutive `"1"` height ending at this row |
|---|---|
| `0` | `3` |
| `1` | `1` |
| `2` | `3` |
| `3` | `2` |
| `4` | `2` |

Now the problem becomes:

Find the largest rectangle in this histogram.

That is exactly LeetCode 84.

So we solve LeetCode 85 by running the histogram solution once per row.

## Building Heights

Maintain an array:

```python
heights = [0] * cols
```

For each row:

If `matrix[row][col] == "1"`:

```python
heights[col] += 1
```

If `matrix[row][col] == "0"`:

```python
heights[col] = 0
```

The reset is necessary because a rectangle of `1`s cannot pass through a `0`.

## Histogram Helper

Given a histogram:

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

we use a monotonic increasing stack.

The stack stores indices whose heights are increasing.

When the current height is smaller than the height at the stack top, we pop the stack and compute the best rectangle where the popped bar is the limiting height.

Use a sentinel `0` at the end to flush all remaining bars.

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

For each popped bar:

```python
height = heights[stack.pop()]
left = stack[-1] if stack else -1
width = i - left - 1
area = height * width
```

## Algorithm

Let:

```python
rows = len(matrix)
cols = len(matrix[0])
```

Initialize:

```python
heights = [0] * cols
best = 0
```

For each row:

1. Update `heights`.
2. Treat `heights` as a histogram.
3. Compute the largest rectangle in that histogram.
4. Update `best`.

Return `best`.

## Walkthrough

Use:

```python
matrix = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"],
]
```

After row `0`:

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

Largest histogram rectangle:

```python
1
```

After row `1`:

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

Largest histogram rectangle:

```python
3
```

The rectangle is the three `1`s at the end of row `1`.

After row `2`:

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

Largest histogram rectangle:

```python
6
```

This corresponds to:

```python
1 1 1
1 1 1
```

After row `3`:

```python
heights = [4, 0, 0, 3, 0]
```

Largest histogram rectangle:

```python
4
```

The global maximum is:

```python
6
```

## Correctness

Every all-`1` rectangle has a bottom row.

When the algorithm processes that bottom row, each column in the rectangle has a height at least equal to the rectangle height, because all cells above the bottom row inside that rectangle are `1`.

So that rectangle appears as a valid rectangle inside the histogram for its bottom row.

The histogram helper computes the largest rectangle for that row. Therefore, when processing the bottom row of any valid matrix rectangle, the algorithm considers an area at least as large as that rectangle.

The algorithm processes every row as a possible bottom row. Therefore, it considers the optimal rectangle.

Also, every rectangle found in a row histogram corresponds to real `1` cells in the matrix, because each histogram height counts consecutive `1`s ending at the current row. So the algorithm never counts a rectangle containing `0`.

Thus the maximum area returned is exactly the largest rectangle containing only `1`s.

## Complexity

Let:

```python
R = number of rows
C = number of columns
```

For each row, we update `C` heights and run a `C`-column histogram scan.

| Metric | Value | Why |
|---|---|---|
| Time | `O(R * C)` | Each row performs linear work over all columns |
| Space | `O(C)` | Heights array and stack both use column-sized space |

## Implementation

```python
class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        cols = len(matrix[0])
        heights = [0] * cols
        best = 0

        def largest_histogram_area(values: list[int]) -> int:
            stack = []
            ans = 0

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

                stack.append(i)

            return ans

        for row in matrix:
            for col in range(cols):
                if row[col] == "1":
                    heights[col] += 1
                else:
                    heights[col] = 0

            best = max(best, largest_histogram_area(heights))

        return best
```

## Code Explanation

We first handle an empty matrix:

```python
if not matrix or not matrix[0]:
    return 0
```

Then create one height per column:

```python
cols = len(matrix[0])
heights = [0] * cols
```

For each row, update the histogram:

```python
if row[col] == "1":
    heights[col] += 1
else:
    heights[col] = 0
```

A `1` extends the vertical run.

A `0` breaks the vertical run.

The helper `largest_histogram_area` is the LeetCode 84 stack algorithm.

This loop adds a sentinel zero:

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

When the current height is smaller than the stack top, we compute completed rectangles:

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

The popped height is the limiting rectangle height:

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

The next smaller bar on the left is:

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

The current index is the next smaller bar on the right.

So the width is:

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

Then update the best histogram area:

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

After each row, update the global answer:

```python
best = max(best, largest_histogram_area(heights))
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maximalRectangle([
        ["1", "0", "1", "0", "0"],
        ["1", "0", "1", "1", "1"],
        ["1", "1", "1", "1", "1"],
        ["1", "0", "0", "1", "0"],
    ]) == 6

    assert s.maximalRectangle([["0"]]) == 0
    assert s.maximalRectangle([["1"]]) == 1
    assert s.maximalRectangle([["0", "0"]]) == 0
    assert s.maximalRectangle([["1", "1"]]) == 2

    assert s.maximalRectangle([
        ["1"],
        ["1"],
        ["1"],
    ]) == 3

    assert s.maximalRectangle([
        ["1", "1", "1"],
        ["1", "1", "1"],
    ]) == 6

    assert s.maximalRectangle([
        ["1", "0", "1"],
        ["1", "1", "1"],
        ["1", "1", "0"],
    ]) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Main matrix | Official example shape |
| `[["0"]]` | Single zero |
| `[["1"]]` | Single one |
| One row of zeros | No rectangle |
| One row of ones | Horizontal rectangle |
| One column of ones | Vertical rectangle |
| Full matrix of ones | Whole matrix is the answer |
| Mixed matrix | Checks height reset and stack logic |