As Far from Land as Possible — Multi-Source BFS

Problem

Find the water cell with the maximum distance to the nearest land cell. Return -1 if no water or no land.

Approach — Multi-Source BFS

Push all land cells into queue (dist=0). BFS outward; last water cell processed has the farthest distance.

Time: O(n²) | Space: O(n²)

Solutions

Python

from collections import deque
class Solution:
    def maxDistance(self, grid: list[list[int]]) -> int:
        n=len(grid)
        q=deque()
        for r in range(n):
            for c in range(n):
                if grid[r][c]==1: q.append((r,c))
        if len(q)==0 or len(q)==n*n: return -1
        ans=-1
        while q:
            r,c=q.popleft()
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                nr,nc=r+dr,c+dc
                if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0:
                    grid[nr][nc]=grid[r][c]+1; ans=grid[nr][nc]-1; q.append((nr,nc))
        return ans

Complexity

Time: O(n²) | Space: O(n²)