# LeetCode 221: Maximal Square

## Problem Restatement

We are given an `m x n` binary matrix.

Each cell contains either:

```text
"0"
"1"
```

We need to find the largest square that contains only `"1"` cells.

Return the area of that square.

The official statement says: given an `m x n` binary matrix filled with `0`s and `1`s, find the largest square containing only `1`s and return its area.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary matrix of strings `"0"` and `"1"` |
| Output | Area of the largest square of only `1`s |
| Shape required | Square, not rectangle |
| Area | `side_length * side_length` |

Example function shape:

```python
def maximalSquare(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 square of `1`s has side length `2`.

So its area is:

```text
2 * 2 = 4
```

Answer:

```python
4
```

Example 2:

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

The largest square has side length `1`.

Answer:

```python
1
```

Example 3:

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

There is no square of `1`s.

Answer:

```python
0
```

## First Thought: Check Every Square

A direct way is:

1. Pick every cell as the top-left corner.
2. Try every possible square size from that cell.
3. Check whether all cells in the square are `"1"`.
4. Track the largest valid square.

This works, but it repeats a lot of checks.

For a large matrix, repeatedly scanning square areas becomes too slow.

## Key Insight

Instead of asking:

```text
What is the largest square starting here?
```

we ask:

```text
What is the largest square ending here?
```

More precisely:

```text
dp[r][c] = side length of the largest all-1 square
           whose bottom-right corner is at cell (r, c)
```

If `matrix[r][c] == "0"`, then no all-1 square can end there:

```text
dp[r][c] = 0
```

If `matrix[r][c] == "1"`, then the square ending there depends on three neighbors:

| Neighbor | Meaning |
|---|---|
| Top | Largest square ending above |
| Left | Largest square ending left |
| Top-left | Largest square ending diagonally |

The current cell can extend a square only if all three directions support it.

So:

```text
dp[r][c] = 1 + min(top, left, top_left)
```

## Why the Minimum Matters

Suppose the current cell is `"1"`.

To form a square of side length `s` ending at this cell, we need:

- a square of side `s - 1` above
- a square of side `s - 1` to the left
- a square of side `s - 1` diagonally above-left

The weakest of these three limits the new square.

For example, if the top supports side `3`, the left supports side `3`, but the diagonal supports only side `1`, then the current square can only become side `2`.

That is why we use the minimum.

## Algorithm

1. Create a DP table with one extra row and one extra column of zeros.
2. Track `max_side`.
3. For each matrix cell:
   - If the cell is `"1"`:
     - compute the side length using top, left, and top-left
     - update `max_side`
   - If the cell is `"0"`:
     - leave the DP value as `0`
4. Return `max_side * max_side`.

The extra row and column avoid boundary checks.

## Walkthrough

Use a smaller matrix:

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

We use a padded DP table.

After processing, the DP values for the original cells are:

```text
1 0 1
1 1 1
1 2 0
```

At cell `(2, 1)`, the value is `2`.

That means the largest square ending there has side length `2`.

The square is:

```text
1 1
1 1
```

The maximum side length is `2`.

Return:

```text
2 * 2 = 4
```

## Correctness

The algorithm defines `dp[r][c]` as the side length of the largest all-1 square whose bottom-right corner is at `(r, c)`.

If `matrix[r][c] == "0"`, no square of `1`s can end at that cell, so the correct value is `0`.

If `matrix[r][c] == "1"`, any square ending there must also have valid all-1 squares touching its top, left, and top-left regions. The largest possible square is limited by the smallest of those three neighboring square sizes. Adding the current cell extends that smallest common support by one.

Therefore the recurrence computes the correct largest square ending at each cell.

The algorithm checks every possible bottom-right corner. The largest square in the whole matrix must have some bottom-right corner, so tracking the maximum DP value finds its side length.

Returning the square of that side length gives the required area.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n)` | Each matrix cell is processed once |
| Space | `O(m * n)` | Full DP table |

Where `m` is the number of rows and `n` is the number of columns.

## Implementation

```python
class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])

        dp = [[0] * (cols + 1) for _ in range(rows + 1)]
        max_side = 0

        for r in range(1, rows + 1):
            for c in range(1, cols + 1):
                if matrix[r - 1][c - 1] == "1":
                    dp[r][c] = 1 + min(
                        dp[r - 1][c],
                        dp[r][c - 1],
                        dp[r - 1][c - 1],
                    )
                    max_side = max(max_side, dp[r][c])

        return max_side * max_side
```

## Code Explanation

Get the matrix dimensions:

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

Create a padded DP table:

```python
dp = [[0] * (cols + 1) for _ in range(rows + 1)]
```

The padding means `dp[r - 1][c]`, `dp[r][c - 1]`, and `dp[r - 1][c - 1]` are always valid.

Track the largest side length:

```python
max_side = 0
```

Process every original matrix cell using shifted DP indices:

```python
for r in range(1, rows + 1):
    for c in range(1, cols + 1):
```

If the current cell is `"1"`:

```python
if matrix[r - 1][c - 1] == "1":
```

compute the largest square ending here:

```python
dp[r][c] = 1 + min(
    dp[r - 1][c],
    dp[r][c - 1],
    dp[r - 1][c - 1],
)
```

Update the best side length:

```python
max_side = max(max_side, dp[r][c])
```

Return area:

```python
return max_side * max_side
```

## Space-Optimized Implementation

We only need the previous row and the current row.

So we can reduce space to `O(n)`.

```python
class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])

        dp = [0] * (cols + 1)
        max_side = 0
        prev_diag = 0

        for r in range(1, rows + 1):
            prev_diag = 0

            for c in range(1, cols + 1):
                top = dp[c]

                if matrix[r - 1][c - 1] == "1":
                    dp[c] = 1 + min(
                        dp[c],
                        dp[c - 1],
                        prev_diag,
                    )
                    max_side = max(max_side, dp[c])
                else:
                    dp[c] = 0

                prev_diag = top

        return max_side * max_side
```

Here:

| Variable | Meaning |
|---|---|
| `dp[c]` before update | Top neighbor |
| `dp[c - 1]` | Left neighbor |
| `prev_diag` | Top-left neighbor |

## Testing

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

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

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

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard matrix | Finds side length `2` |
| Diagonal ones | Only side length `1` |
| Single zero | No square |
| Single one | Area `1` |
| `2 x 2` all ones | Full matrix square |
| `2 x 3` all ones | Largest square side is `2` |