Largest Plus Sign Python Solution with Tests

lcpy gen -n 764   # by problem number
lcpy gen -s largest_plus_sign   # by problem name

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.

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

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)