1162. As Far from Land as Possible - cocoder39/coco39_LC GitHub Wiki

1162. As Far from Land as Possible

Option 1: find the closest land from each water and find the max value. Time complexity is to execute bfs n^2 times for each water and each bfs traverses n^2 nodes so in total time complexity is O(n ^ 4)

Option 2: convert the problem to find furthest water to all lands => multiple source bfs => time complexity is O(n ^ 2)

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        visited = set()
        queue = collections.deque()
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    visited.add((i, j))
                    queue.append((i, j))
        if len(queue) == n * n or len(queue) == 0:
            return -1
                    
        dist = 0
        while queue:
            sz = len(queue)
            for i in range(sz):
                cur_r, cur_c = queue.popleft()
                for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    if 0 <= cur_r+x < n and 0 <= cur_c+y < n and (cur_r+x, cur_c+y) not in visited:
                        visited.add((cur_r+x, cur_c+y))
                        queue.append((cur_r+x, cur_c+y))
            dist += 1
        
        return dist - 1