TOP = 0
RIGHT = 1
BOTTOM = 2
LEFT = 3

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        mines = set(map(tuple, mines))
        # We have a sentry value and we make use of the fact that in Python
        # the index -1 is the same as the last index in the array
        grid = [[[0] * 4 for y in range(n + 1)] for x in range(n + 1)]

        for x in range(n):
            for y in range(n):
                if (x, y) in mines:
                    continue
                grid[x][y][LEFT] = grid[x-1][y][LEFT] + 1
                grid[x][y][TOP] = grid[x][y-1][TOP] + 1

        for x in range(n - 1, -1, -1):
            for y in range(n - 1, -1, -1):
                if (x, y) in mines:
                    continue
                grid[x][y][RIGHT] = grid[x+1][y][RIGHT] + 1
                grid[x][y][BOTTOM] = grid[x][y+1][BOTTOM] + 1

        return max(min(grid[x][y]) for x in range(n) for y in range(n))