As Far from Land as Possible

medium bfs grid

Problem

Given an n × n grid where 1 is land and 0 is water, return the maximum Manhattan distance from any water cell to its nearest land cell. If no land or no water exists, return -1.

Inputgrid = [[1,0,1],[0,0,0],[1,0,1]]

Output2

The center water cell is distance 2 from any land.

grid (rows ';', cells ',')

from collections import deque
def max_distance(grid):
    n = len(grid)
    q = deque()
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                q.append((i, j, 0))
    if not q or len(q) == n * n: return -1
    seen = [[False]*n for _ in range(n)]
    best = 0
    while q:
        i, j, d = q.popleft()
        if seen[i][j]: continue
        seen[i][j] = True
        best = max(best, d)
        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
            ni, nj = i+di, j+dj
            if 0 <= ni < n and 0 <= nj < n and not seen[ni][nj] and grid[ni][nj] == 0:
                q.append((ni, nj, d+1))
    return best

function maxDistance(grid) {
  const n = grid.length;
  const q = [];
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === 1) q.push([i, j, 0]);
  if (q.length === 0 || q.length === n * n) return -1;
  const seen = Array.from({length: n}, () => Array(n).fill(false));
  let best = 0;
  while (q.length) {
    const [i, j, d] = q.shift();
    if (seen[i][j]) continue;
    seen[i][j] = true;
    best = Math.max(best, d);
    for (const [di, dj] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const ni = i+di, nj = j+dj;
      if (ni>=0 && ni<n && nj>=0 && nj<n && !seen[ni][nj] && grid[ni][nj] === 0)
        q.push([ni, nj, d+1]);
    }
  }
  return best;
}

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) q.offer(new int[]{i, j, 0});
        if (q.isEmpty() || q.size() == n * n) return -1;
        boolean[][] seen = new boolean[n][n];
        int best = 0;
        int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int i = t[0], j = t[1], d = t[2];
            if (seen[i][j]) continue;
            seen[i][j] = true;
            best = Math.max(best, d);
            for (int[] dd : D) {
                int ni = i+dd[0], nj = j+dd[1];
                if (ni>=0 && ni<n && nj>=0 && nj<n && !seen[ni][nj] && grid[ni][nj] == 0)
                    q.offer(new int[]{ni, nj, d+1});
            }
        }
        return best;
    }
}

int maxDistance(vector<vector<int>>& grid) {
    int n = grid.size();
    queue<tuple<int,int,int>> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == 1) q.emplace(i, j, 0);
    if (q.empty() || (int)q.size() == n * n) return -1;
    vector<vector<bool>> seen(n, vector<bool>(n, false));
    int best = 0;
    int D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.empty()) {
        auto [i, j, d] = q.front(); q.pop();
        if (seen[i][j]) continue;
        seen[i][j] = true;
        best = max(best, d);
        for (auto& dd : D) {
            int ni = i+dd[0], nj = j+dd[1];
            if (ni>=0 && ni<n && nj>=0 && nj<n && !seen[ni][nj] && grid[ni][nj] == 0)
                q.emplace(ni, nj, d+1);
        }
    }
    return best;
}

Explanation

We want the water cell that is farthest from any land. Instead of measuring each water cell separately, we flood outward from all land cells at once and watch how far the water frontier gets — the last distance reached is the answer.

This is multi-source BFS. Every land cell goes into the queue with distance 0. We then expand to unseen water neighbours, each one step farther than the cell it came from, and keep track of the largest distance in best.

Because BFS spreads evenly in all directions, the first time a water cell is reached it is reached by its nearest land, so its distance is correct. We also handle the edge case: if there is no land or no water (queue is empty or full), the answer is -1.

Example: [[1,0,1],[0,0,0],[1,0,1]]. Land sits in the four corners; the water cells fill in distance 1, and the very center cell is reached at distance 2, which is the maximum, so the answer is 2.

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