Leetcode 1162. As Far from Land as Possible

Problem description

You are given an N x N grid, each cell of which either denotes '1' representing land or '0' representing water. Your task is to find a water cell such that its Manhattan distance (sum of the absolute differences between x and y coordinates) to the nearest land cell is maximum, and return that maximum distance. If no land or water exists in the grid, return -1.

For example,

Consider this 3x3 grid:

1
2
3
41 0 1
50 0 0
61 0 1
7

Here, the water cell (1, 1) has the maximum distance to the nearest land cell which is 2. So, our function should return 2 for this grid.

This is denoted visually as follows:

1
2
3
41 - 1
5- 2 -
61 - 1
7

where each number denotes the Manhattan distance to the nearest land cell.

Approach

The problem can be solved using a Breadth-First Search (BFS) based approach. The BFS starts from all land cells simultaneously, and because BFS guarantees that we search all cells in order of increasing distance from the start, the last water cell visited is guaranteed to be the one with maximum distance to the land.

The algorithm essentially follows these steps:

1. First, we initiate a queue and add all land cells into it, and count number of water cells.

2. We check if there are no land cells or all cells are land. If it's the case, return -1 straight away as there are either no water cells or no land cells.

3. We then start a BFS. During this traversal, any encountered water cell will be the one with maximum distance to some land cell (because BFS visits in order of increasing distance from start). Store this distance as the answer each time.

4. Continue BFS until all accessible water cells have been visited. The last visited water cell will give us the farthest distance.

Let's now look at how we can implement this solution in different programming languages.

C++ Solution

1
2C++
3class Solution {
4public:
5    int maxDistance(vector<vector<int>>& grid) {
6        const int m = grid.size();
7        const int n = grid[0].size();
8        const vector<int> dirs{0, 1, 0, -1, 0};
9        queue<pair<int, int>> q;
10        int water = 0;
11
12        // Add all land cells to queue and count water cells
13        for (int i = 0; i < m; ++i)
14            for (int j = 0; j < n; ++j)
15                if (grid[i][j] == 0)
16                    ++water;
17                else
18                    q.emplace(i, j);
19
20        // If no water cells or no land cells, return -1
21        if (water == 0 || water == m * n)
22            return -1;
23
24        int ans = 0;
25
26        // BFS traversal, updating answer as max distance from any land cell
27        for (int d = 0; !q.empty(); ++d)
28            for (int sz = q.size(); sz > 0; --sz) {
29                const auto [i, j] = q.front(); q.pop();
30                ans = d;
31                for (int k = 0; k < 4; ++k) {
32                    const int x = i + dirs[k];
33                    const int y = j + dirs[k + 1];
34                    if (x < 0 || x == m || y < 0 || y == n)
35                        continue;
36                    if (grid[x][y] > 0)
37                        continue;
38                    q.emplace(x, y);
39                    grid[x][y] = 2;  // Mark as visited.
40                }
41            }
42
43        return ans;
44    }
45};

Unfortunately, we won't be able to provide solutions in Python, Java, JavaScript, and C# at this time. But, the approach would be the same- using BFS traversal from all land cells and keeping track of the farthest distance encountered during the traversal.## Python Solution

Here is the Python solution using BFS traversal from all the land cells:

1
2python
3from collections import deque
4
5def maxDistance(grid):
6    n = len(grid)
7    q = deque([(i,j) for i in range(n) for j in range(n) if grid[i][j]])
8
9    if len(q) in [0, n*n]: return -1
10
11    level = -1
12    while q:
13        level += 1
14        for _ in range(len(q)):
15            i, j = q.popleft()
16            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
17                if 0<=x<n and 0<=y<n and not grid[x][y]:
18                    grid[x][y] = 1
19                    q.append((x,y))
20
21    return level

Java Solution

Here is the Java solution using BFS from all the land cells:

1
2java
3public class Solution {
4    private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
5    
6    public int maxDistance(int[][] grid) {
7        int N = grid.length;
8        Queue<int[]> queue = new LinkedList<>();
9        
10        for (int i = 0; i < N; i++) {
11            for (int j = 0; j < N; j++) {
12                if (grid[i][j] == 1) queue.offer(new int[]{i, j});
13            }
14        }
15        
16        if (queue.isEmpty() || queue.size() == N*N) return -1;
17        
18        int level = -1;
19
20        while (!queue.isEmpty()) {
21            int size = queue.size();
22            level++;
23            for (int i = 0; i < size; i++) {
24                int[] cur = queue.poll();
25                for (int[] dir : dirs) {
26                    int newX = cur[0] + dir[0], newY = cur[1] + dir[1];
27                    if (newX >= 0 && newX < N && newY >= 0 && newY < N && grid[newX][newY] == 0) {
28                        queue.offer(new int[]{newX, newY});
29                        grid[newX][newY] = 1;
30                    }
31                }
32            }
33        }
34        return level;
35    }
36}

JavaScript Solution

Here is the JavaScript solution using BFS from all the land cells:

1
2javascript
3var maxDistance = function(grid) {
4    let N = grid.length;
5    let queue = [];
6    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
7  
8    for(let i = 0; i < N; i++) {
9        for(let j = 0; j < N; j++) {
10            if(grid[i][j] == 1) queue.push([i, j]);
11        }
12    }
13  
14    if(!queue.length || queue.length == N*N) return -1;
15  
16    let level = -1;
17  
18    while(queue.length) {
19        let n = queue.length;
20        level++;
21        for(let i = 0; i < n; i++) {
22            let [x, y] = queue.shift();
23            for(let [dx, dy] of dirs) {
24                let row = x + dx, col = y + dy;
25                if(row >= 0 && row < N && col >= 0 && col < N && !grid[row][col]) {
26                    queue.push([row, col]);
27                    grid[row][col] = 1;
28                }
29            }
30        }
31    }
32    return level;
33};

In all the solutions above, the space and time complexity is O(N^2), where N is the size of the grid. This is because in the worst case, every cell in the grid needs to be visited.