As Far from Land as Possible

Problem Id: 1162 Difficulty: Medium


Intuition

Solution


class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        # Dji alg
        queue = collections.deque([])
        rows = len(grid)
        cols = len(grid[0])
        for i in range(rows):
            for j in range(cols):
                if grid[i][j]:
                    queue.append((i, j))

        if len(queue) == rows * cols or len(queue) == 0:
            return -1

        while queue:
            x, y = queue.popleft()
            for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if (0 <= i < rows) and (0 <= j < cols):
                    if grid[i][j] == 0:
                        grid[i][j] = grid[x][y] + 1
                        queue.append((i, j))
        return max([max(row) for row in grid]) - 1