Sort cells by elevation. Union until start connects to end.
def swimInWater(grid): n = len(grid) parent = list(range(n * n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
parent[find(x)] = find(y)
def idx(r, c):
return r * n + c
cells = sorted((grid[r][c], r, c) for r in range(n) for c in range(n))
added = [[False] * n for _ in range(n)]
for elev, r, c in cells:
added[r][c] = True
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and added[nr][nc]:
union(idx(r, c), idx(nr, nc))
if find(idx(0, 0)) == find(idx(n-1, n-1)):
return elev
return -1
time, space.