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.
1from collections import deque
2
3def maxDistance(grid):
4 n = len(grid)
5 queue = deque()
6 hasWater = False
7
8 for i in range(n):
9 for j in range(n):
10 if grid[i][j] == 1:
11 queue.append((i, j))
12 else:
13 hasWater = True
14
15 if len(queue) == 0 or not hasWater:
16 return -1
17
18 distance = -1
19 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
20
21 while queue:
22 size = len(queue)
23 for _ in range(size):
24 x, y = queue.popleft()
25 for dx, dy in directions:
26 nx, ny = x + dx, y + dy
27 if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
28 grid[nx][ny] = 1
29 queue.append((nx, ny))
30 distance += 1
31
32 return distance
33This Python solution uses a deque from the collections module to efficiently perform BFS. The grid's cells are converted to land as they are processed, leveraging BFS layers to determine the farthest water distance.