Sponsored
Sponsored
This approach uses BFS starting from all land cells simultaneously. We can think of the lands spreading out like waves in unison into the water cells, each wave representing a unit of distance. This helps us efficiently compute the farthest distance of a water cell from land.
The time complexity is O(n2), where n is the dimension of the grid, as each cell is visited once. The space complexity is also O(n2) due to the queue that can store all cells in the grid.
1function maxDistance(grid) {
2 const n = grid.length;
3 const queue = [];
4 let hasWater = false;
5
6 for (let i = 0; i < n; i++) {
7 for (let j = 0; j < n; j++) {
8 if (grid[i][j] === 1) {
9 queue.push([i, j]);
10 } else {
11 hasWater = true;
12 }
13 }
14 }
15
16 if (queue.length === 0 || !hasWater) return -1;
17
18 const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
19 let distance = -1;
20
21 while (queue.length > 0) {
22 const size = queue.length;
23 for (let k = 0; k < size; k++) {
24 const [x, y] = queue.shift();
25 for (const [dx, dy] of directions) {
26 const nx = x + dx, ny = y + dy;
27 if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] === 0) {
28 grid[nx][ny] = 1;
29 queue.push([nx, ny]);
30 }
31 }
32 }
33 distance++;
34 }
35
36 return distance;
37}
38JavaScript's implementation uses a simple queue array to perform BFS. It checks all directions from each cell and expands the queue with neighbors, computing max distance by counting BFS layers.