Problem statement

https://leetcode.com/problems/as-far-from-land-as-possible/

Solution

Use multi-source bfs, where we start from all lands.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def maxDistance(self, grid):
        m, n = len(grid), len(grid[0])
        q = deque([(0, i, j) for i in range(m) for j in range(n) if grid[i][j] == 1])    
        if len(q) == m * n or len(q) == 0: return -1
        ans = 0

        V = set()
        while q:
            dist, i, j = q.popleft()
            ans = max(dist, ans)
            for x, y in (1, 0), (-1, 0), (0, 1), (0, -1):
                xi, yj = x+i, y+j
                if 0 <= xi < m and 0 <= yj < n and grid[xi][yj] == 0 and (xi, yj) not in V:
                    V.add((xi, yj))
                    q += [(dist + 1, xi, yj)]
                    grid[xi][yj] = 0

        return ans