Problem statement

https://binarysearch.com/problems/Farthest-Point-From-Water/

Solution

Almost the same as Leetcode 1162. As Far from Land as Possible, just change 0 with 1. Idea is to start from all water points with bfs.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(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] == 0])    
        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] == 1 and (xi, yj) not in V:
                    V.add((xi, yj))
                    q += [(dist + 1, xi, yj)]
                    grid[xi][yj] = 0

        return ans