> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Largest Plus Sign Python Solution with Tests

> Tested Python solution for LeetCode 764 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 764, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/largest-plus-sign/description/).

Generate this problem as a practice environment: tested reference solution, 17 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 764   # by problem number
lcpy gen -s largest_plus_sign   # by problem name
```

## Problem

You are given an integer `n`. You have an `n x n` binary grid `grid` with all values initially `1`'s except for some indices given in the array `mines`. The `i^th` element of the array `mines` is defined as `mines[i] = [x_i, y_i]` where `grid[x_i][y_i] == 0`.

Return *the order of the largest **axis-aligned** plus sign of* 1\*'s contained in\* `grid`. If there is none, return `0`.

An **axis-aligned plus sign** of `1`'s of order `k` has some center `grid[r][c] == 1` along with four arms of length `k - 1` going up, down, left, and right, and made of `1`'s. Note that there could be `0`'s or `1`'s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for `1`'s.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/06/13/plus1-grid.jpg)

```
Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.
```

![Example 2](https://assets.leetcode.com/uploads/2021/06/13/plus2-grid.jpg)

```
Input: n = 1, mines = [[0,0]]
Output: 0
Explanation: There is no plus sign, so return 0.
```

### Constraints

* 1 \<= n \<= 500
* 1 \<= mines.length \<= 5000
* 0 \<= xi, yi \< n
* All the pairs (xi, yi) are unique.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/largest_plus_sign/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/largest_plus_sign/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^2)
    # Space: O(n^2)
    def order_of_largest_plus_sign(self, n: int, mines: list[list[int]]) -> int:
        blocked = {(x, y) for x, y in mines}

        # dp[r][c] = length of the run of 1s ending at (r, c) in the current direction
        dp = [[n] * n for _ in range(n)]

        for r in range(n):
            # left to right
            run = 0
            for c in range(n):
                run = 0 if (r, c) in blocked else run + 1
                dp[r][c] = min(dp[r][c], run)
            # right to left
            run = 0
            for c in range(n - 1, -1, -1):
                run = 0 if (r, c) in blocked else run + 1
                dp[r][c] = min(dp[r][c], run)

        for c in range(n):
            # top to bottom
            run = 0
            for r in range(n):
                run = 0 if (r, c) in blocked else run + 1
                dp[r][c] = min(dp[r][c], run)
            # bottom to top
            run = 0
            for r in range(n - 1, -1, -1):
                run = 0 if (r, c) in blocked else run + 1
                dp[r][c] = min(dp[r][c], run)

        return max(max(row) for row in dp)
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) | O(n^2) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.