# LeetCode 764: Largest Plus Sign

## Problem Restatement

We are given an integer `n`.

There is an `n x n` grid where every cell is initially `1`.

Some cells are mines. Each mine is given as:

```python
[x, y]
```

That means:

```python
grid[x][y] = 0
```

We need to find the largest axis-aligned plus sign made only of `1`s.

A plus sign of order `k` has:

1. one center cell
2. an upward arm of length `k - 1`
3. a downward arm of length `k - 1`
4. a left arm of length `k - 1`
5. a right arm of length `k - 1`

The center is included in the order.

So a single `1` cell is a plus sign of order `1`.

If there is no plus sign, return `0`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `n`, the grid size |
| Input | `mines`, positions that contain `0` |
| Output | The largest plus sign order |
| Grid | Initially all `1`s except mine cells |
| Plus sign | Must be axis-aligned |

Example function shape:

```python
def orderOfLargestPlusSign(n: int, mines: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
n = 5
mines = [[4, 2]]
```

Output:

```python
2
```

The grid is mostly `1`s, except cell `(4, 2)`.

A plus sign of order `2` needs one cell in each direction from its center.

One possible center is `(2, 2)`:

```text
    1
    1
1 1 1 1 1
    1
```

But an order `3` plus sign would need two cells in every direction. The mine at `(4, 2)` blocks the downward arm for center `(2, 2)`, so the largest order is `2`.

Example 2:

```python
n = 1
mines = [[0, 0]]
```

Output:

```python
0
```

The only cell is a mine, so there is no plus sign.

## First Thought: Try Every Center and Every Size

A direct solution is to try every cell as a center.

For each center, we try to grow a plus sign outward.

For every possible order, check whether the four arms are all `1`s.

This works logically, but it is too slow.

There are `n^2` possible centers. For each center, checking arms can take up to `O(n)` time. With repeated checks, the solution can become too expensive.

We need to precompute useful information.

## Key Insight

For a cell `(r, c)` to be the center of a plus sign of order `k`, it needs at least `k` consecutive `1`s in all four directions, counting the center itself.

That means we need:

```text
left_count[r][c]  >= k
right_count[r][c] >= k
up_count[r][c]    >= k
down_count[r][c]  >= k
```

So the largest plus sign centered at `(r, c)` is:

```text
min(left_count, right_count, up_count, down_count)
```

Then the answer is the maximum of this value over all cells.

## Directional Counts

For each cell, compute how many consecutive `1`s end at that cell from each direction.

Example row:

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

Left-to-right counts are:

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

Right-to-left counts are:

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

We do the same vertically for top-to-bottom and bottom-to-top.

Instead of storing four separate matrices, we can store one matrix `dp`.

Initialize every non-mine cell to `n`.

Then each directional scan updates:

```python
dp[r][c] = min(dp[r][c], count)
```

After all four scans, `dp[r][c]` stores the smallest directional count, which is the largest plus order centered at that cell.

## Algorithm

1. Create an `n x n` matrix `dp`, initially filled with `n`.
2. Mark all mines as `0`.
3. For each row:
   1. scan left to right
   2. scan right to left
4. For each column:
   1. scan top to bottom
   2. scan bottom to top
5. During each scan, keep a count of consecutive `1`s.
6. If a cell is a mine, reset the count to `0`.
7. Otherwise, increase the count and update `dp`.
8. Return the maximum value in `dp`.

## Correctness

For any cell `(r, c)`, a plus sign of order `k` centered there exists exactly when there are at least `k` consecutive `1`s including `(r, c)` in all four directions.

The left-to-right scan computes the number of consecutive `1`s ending at each cell from the left. The right-to-left scan computes the same quantity from the right. The vertical scans compute the corresponding upward and downward counts.

Each scan updates `dp[r][c]` with the minimum count seen so far. After all four scans, `dp[r][c]` equals the minimum of the four arm counts. Therefore, it is exactly the largest order of a plus sign centered at `(r, c)`.

The algorithm takes the maximum value over all cells. Since every valid plus sign has some center, and every center's largest possible order is represented in `dp`, the returned value is exactly the order of the largest plus sign in the grid.

## Complexity

Let `n` be the grid size.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | We scan the grid a constant number of times |
| Space | `O(n^2)` | The `dp` matrix stores one value per cell |

## Implementation

```python
class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: list[list[int]]) -> int:
        dp = [[n] * n for _ in range(n)]

        for r, c in mines:
            dp[r][c] = 0

        for r in range(n):
            count = 0
            for c in range(n):
                if dp[r][c] == 0:
                    count = 0
                else:
                    count += 1
                    dp[r][c] = min(dp[r][c], count)

            count = 0
            for c in range(n - 1, -1, -1):
                if dp[r][c] == 0:
                    count = 0
                else:
                    count += 1
                    dp[r][c] = min(dp[r][c], count)

        for c in range(n):
            count = 0
            for r in range(n):
                if dp[r][c] == 0:
                    count = 0
                else:
                    count += 1
                    dp[r][c] = min(dp[r][c], count)

            count = 0
            for r in range(n - 1, -1, -1):
                if dp[r][c] == 0:
                    count = 0
                else:
                    count += 1
                    dp[r][c] = min(dp[r][c], count)

        answer = 0

        for row in dp:
            answer = max(answer, max(row))

        return answer
```

## Code Explanation

We create the matrix:

```python
dp = [[n] * n for _ in range(n)]
```

Using `n` means every cell starts with the largest possible count. Directional scans will reduce it.

Then mines are marked as zero:

```python
for r, c in mines:
    dp[r][c] = 0
```

A mine cannot be part of any plus sign.

For each row, we scan from left to right:

```python
count = 0

for c in range(n):
    if dp[r][c] == 0:
        count = 0
    else:
        count += 1
        dp[r][c] = min(dp[r][c], count)
```

The variable `count` tells how many consecutive non-mine cells we have seen so far.

When we hit a mine, the streak resets.

The right-to-left scan does the same thing from the other side.

Then the column scans do the same thing vertically:

```python
for c in range(n):
```

After all four scans, each `dp[r][c]` contains the smallest arm length available in any direction.

Finally, we take the maximum:

```python
answer = 0

for row in dp:
    answer = max(answer, max(row))
```

That value is the largest plus sign order.

## Testing

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

    assert s.orderOfLargestPlusSign(5, [[4, 2]]) == 2

    assert s.orderOfLargestPlusSign(1, [[0, 0]]) == 0

    assert s.orderOfLargestPlusSign(1, []) == 1

    assert s.orderOfLargestPlusSign(2, []) == 1

    assert s.orderOfLargestPlusSign(3, []) == 2

    assert s.orderOfLargestPlusSign(
        3,
        [[1, 0], [1, 1], [1, 2]],
    ) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 5`, mine at `[4,2]` | Main example |
| Single mined cell | No plus sign exists |
| Single open cell | Order `1` is valid |
| `2 x 2` grid | No cell can have four arms, but order `1` exists |
| `3 x 3` empty grid | Center forms order `2` |
| Blocked middle row | Only single-cell plus signs remain |