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.
1import java.util.LinkedList;
2import java.util.Queue;
3
4public class Solution {
5 public int maxDistance(int[][] grid) {
6 int n = grid.length;
7 Queue<int[]> queue = new LinkedList<>();
8 boolean hasWater = false;
9
10 for (int i = 0; i < n; i++) {
11 for (int j = 0; j < n; j++) {
12 if (grid[i][j] == 1) {
13 queue.offer(new int[]{i, j});
14 } else {
15 hasWater = true;
16 }
17 }
18 }
19
20 if (queue.size() == n * n || !hasWater) return -1;
21
22 int distance = -1;
23 int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
24
25 while (!queue.isEmpty()) {
26 int size = queue.size();
27 for (int k = 0; k < size; k++) {
28 int[] cell = queue.poll();
29 for (int[] direction : directions) {
30 int x = cell[0] + direction[0];
31 int y = cell[1] + direction[1];
32 if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] == 0) {
33 grid[x][y] = 1;
34 queue.offer(new int[]{x, y});
35 }
36 }
37 }
38 distance++;
39 }
40
41 return distance;
42 }
43}
44The Java solution utilizes a queue for BFS, initially adding all land cell coordinates. It tracks the maximum distance by counting levels of BFS iterations, updating water cells to land as BFS proceeds.