As Far from Land as Possible | Problems

Given an N×N grid containing only 0s (water) and 1s (land), find the water cell with the maximum distance to the nearest land cell. Return that distance, or -1 if no water or no land exists.

Example: grid = [[1,0,1],[0,0,0],[1,0,1]] → Output: 2

Sample Input

—

Sample Output

—

Constraints

n == grid.length == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

Test Cases

Case 1

Args: [[[1,0,1],[0,0,0],[1,0,1]]] Expected: 2

Case 2

Args: [[[1,0,0],[0,0,0],[0,0,0]]] Expected: 4

Topics

Graph BFS DFS

Multi-source BFS

Start BFS from all land cells simultaneously and expand outward.

function maxDistance(grid) {
  const n = grid.length, q = [];
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === 1) q.push([i, j]);
  if (q.length === 0 || q.length === n * n) return -1;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  let dist = -1;
  while (q.length) {
    dist++;
    const size = q.length;
    for (let k = 0; k < size; k++) {
      const [r, c] = q.shift();
      for (const [dr, dc] of dirs) {
        const nr = r+dr, nc = c+dc;
        if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
          grid[nr][nc] = 1; q.push([nr, nc]);
        }
      }
    }
  }
  return dist;
}

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

Saved in this browser only. Private to you.