As Far from Land as Possible Medium 0 attempts
LeetCode ↗

As Far from Land as Possible

Medium GraphBFSDFS LeetCode

You're given an N x N grid where each cell is either 0 (water) or 1 (land). Using Manhattan distance measured over horizontal/vertical moves, find the water cell that is as far as possible from any land cell, and return that distance. If the grid is entirely water or entirely land, return -1.

Input Format
Implement maxDistance(grid). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
grid = [[1,0,1],[0,0,0],[1,0,1]]
Output
2

Example 2

Input
grid = [[1,0,0],[0,0,0],[0,0,0]]
Output
4
Constraints
  • n == grid.length == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] is 0 or 1
Test Cases (2)
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
GraphBFSDFS

Multi-source BFS

Start BFS from all land cells simultaneously and expand outward.

javascript
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;
  let head = 0;
  while (head < q.length) {
    dist++;
    const size = q.length - head;
    for (let k = 0; k < size; k++) {
      const [r, c] = q[head++];
      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.

JavaScript