Description
An n x n grid has distinct elevations from 0 through n^2 - 1. At time t, you can traverse cells of elevation at most t in four directions. Find the earliest time a path connects the top-left and bottom-right cells.
Solution
def swim_in_water(grid):
n = len(grid)
def reachable(level):
seen = {(0, 0)}
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for x, y in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= x < n and 0 <= y < n and (x, y) not in seen and grid[x][y] <= level:
seen.add((x, y))
stack.append((x, y))
return False
left, right = max(grid[0][0], grid[-1][-1]), n * n - 1
while left < right:
middle = (left + right) // 2
if reachable(middle):
right = middle
else:
left = middle + 1
return leftExamples
Example 1
- Input
[[[0,2],[1,3]]]- Output
3
The destination requires water level 3.
Example 2
- Input
[[[0]]]- Output
0
Start and destination are the same cell.
Example 3
- Input
[[[3,2],[0,1]]]- Output
3
The starting elevation itself requires level 3.
Approach
Binary-search the allowed water level. For a candidate, flood-fill all reachable cells no higher than that level. Reachability is monotone: once a level works, all higher levels work.
Time & space
O(n^2 log(n^2 + 1)) time and O(n^2) auxiliary space, where n is grid width.