Skip to content

As Far from Land as Possible⚓︎

Link

Description⚓︎

Given an n x n gridcontaining only values 0 and 1, where0 represents waterand 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|.

Example 1:

Ex1

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:

Ex2

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.

Constraints:

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

Solution⚓︎

BFS⚓︎

 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
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        queue<pair<int, int>> que;
        vector<vector<bool>> visited(n, vector<bool>(m, false));

        int numOfSeas = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    visited[i][j] = true;
                    que.emplace(i, j);
                } else {
                    numOfSeas++;
                }
            }
        }

        if (numOfSeas == 0 || numOfSeas == n * m) {
            return -1;
        }

        array<int, 5> moves{-1, 0, 1, 0, -1};
        int level = 0;

        while (!que.empty()) {
            level++;
            int queueSize = que.size();

            while (queueSize--) {
                auto [x, y] = que.front();
                que.pop();

                for (int i = 0; i < 4; i++) {
                    int nextX = x + moves[i], nextY = y + moves[i + 1];
                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && !visited[nextX][nextY]) {
                        visited[nextX][nextY] = true;
                        que.emplace(nextX, nextY);
                    }
                }
            }
        }

        return level - 1;
    }
};
  • Time complexity: \(O(NM)\);
  • Space complexity: \(O(NM)\).