Problem

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

Examples

Example 1:

$$ \begin{bmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix} $$

1
2
3

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

$$ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} $$

1
2
3

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

Solution

Method 1 – Multi-Source Breadth-First Search (1)

Intuition

The key idea is to treat all land cells as sources and perform a BFS to expand outwards, layer by layer. The first time a water cell is reached, its distance from land is recorded. The farthest water cell from any land will be the answer.

Approach

  1. Add all land cells to a queue and mark them as visited.
  2. For each cell in the queue, expand to its four neighbors (up, down, left, right) if they are water and unvisited, marking them as visited and adding them to the queue.
  3. Track the distance as you expand each layer.
  4. If there are no water or no land cells, return -1.
  5. The answer is the last distance assigned to a water cell.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size(), ans = -1;
        queue<pair<int, int>> q;
        vector<vector<bool>> vis(n, vector<bool>(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) q.push({i, j}), vis[i][j] = true;
        if (q.empty() || q.size() == n * n) return -1;
        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!q.empty()) {
            int sz = q.size();
            ++ans;
            for (int k = 0; k < sz; ++k) {
                auto [i, j] = q.front(); q.pop();
                for (auto& d : dirs) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 0) {
                        vis[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func maxDistance(grid [][]int) int {
    n := len(grid)
    vis := make([][]bool, n)
    for i := range vis {
        vis[i] = make([]bool, n)
    }
    q := [][2]int{}
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                q = append(q, [2]int{i, j})
                vis[i][j] = true
            }
        }
    }
    if len(q) == 0 || len(q) == n*n {
        return -1
    }
    dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
    ans := -1
    for len(q) > 0 {
        sz := len(q)
        ans++
        for k := 0; k < sz; k++ {
            i, j := q[0][0], q[0][1]
            q = q[1:]
            for _, d := range dirs {
                x, y := i+d[0], j+d[1]
                if x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 0 {
                    vis[x][y] = true
                    q = append(q, [2]int{x, y})
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length, ans = -1;
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) { q.add(new int[]{i, j}); vis[i][j] = true; }
        if (q.isEmpty() || q.size() == n * n) return -1;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!q.isEmpty()) {
            int sz = q.size();
            ans++;
            for (int k = 0; k < sz; k++) {
                int[] cur = q.poll();
                for (int[] d : dirs) {
                    int x = cur[0] + d[0], y = cur[1] + d[1];
                    if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 0) {
                        vis[x][y] = true;
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun maxDistance(grid: Array<IntArray>): Int {
        val n = grid.size
        val vis = Array(n) { BooleanArray(n) }
        val q = ArrayDeque<Pair<Int, Int>>()
        for (i in 0 until n)
            for (j in 0 until n)
                if (grid[i][j] == 1) { q.add(i to j); vis[i][j] = true }
        if (q.isEmpty() || q.size == n * n) return -1
        val dirs = arrayOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)
        var ans = -1
        while (q.isNotEmpty()) {
            repeat(q.size) {
                val (i, j) = q.removeFirst()
                for ((dx, dy) in dirs) {
                    val x = i + dx; val y = j + dy
                    if (x in 0 until n && y in 0 until n && !vis[x][y] && grid[x][y] == 0) {
                        vis[x][y] = true
                        q.add(x to y)
                    }
                }
            }
            ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maxDistance(self, grid: list[list[int]]) -> int:
        n = len(grid)
        vis = [[False]*n for _ in range(n)]
        q = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]
        for i, j in q:
            vis[i][j] = True
        if not q or len(q) == n*n:
            return -1
        ans = -1
        while q:
            nq = []
            ans += 1
            for i, j in q:
                for dx, dy in ((0,1),(1,0),(0,-1),(-1,0)):
                    x, y = i+dx, j+dy
                    if 0 <= x < n and 0 <= y < n and not vis[x][y] and grid[x][y] == 0:
                        vis[x][y] = True
                        nq.append((x, y))
            q = nq
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

impl Solution {
    pub fn max_distance(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut vis = vec![vec![false; n]; n];
        let mut q = vec![];
        for i in 0..n {
            for j in 0..n {
                if grid[i][j] == 1 {
                    q.push((i, j));
                    vis[i][j] = true;
                }
            }
        }
        if q.is_empty() || q.len() == n * n {
            return -1;
        }
        let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
        let mut ans = -1;
        while !q.is_empty() {
            let sz = q.len();
            ans += 1;
            for _ in 0..sz {
                let (i, j) = q.remove(0);
                for (dx, dy) in dirs.iter() {
                    let x = i as i32 + dx;
                    let y = j as i32 + dy;
                    if x >= 0 && x < n as i32 && y >= 0 && y < n as i32 {
                        let (x, y) = (x as usize, y as usize);
                        if !vis[x][y] && grid[x][y] == 0 {
                            vis[x][y] = true;
                            q.push((x, y));
                        }
                    }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    maxDistance(grid: number[][]): number {
        const n = grid.length;
        const vis = Array.from({length: n}, () => Array(n).fill(false));
        let q: [number, number][] = [];
        for (let i = 0; i < n; i++)
            for (let j = 0; j < n; j++)
                if (grid[i][j] === 1) { q.push([i, j]); vis[i][j] = true; }
        if (q.length === 0 || q.length === n * n) return -1;
        let ans = -1;
        while (q.length) {
            let nq: [number, number][] = [];
            ans++;
            for (const [i, j] of q) {
                for (const [dx, dy] of [[0,1],[1,0],[0,-1],[-1,0]]) {
                    const x = i + dx, y = j + dy;
                    if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && grid[x][y] === 0) {
                        vis[x][y] = true;
                        nq.push([x, y]);
                    }
                }
            }
            q = nq;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), since each cell is visited at most once.
  • 🧺 Space complexity: O(n^2), for the queue and visited matrix.