Process cells in order of increasing elevation. At each step, union the cell with its neighbors (if they're already processed):
def swimInWater(grid):
n = len(grid)
uf = UnionFind(n * n)
# Sort cells by elevation
cells = []
for i in range(n):
for j in range(n):
cells.append((grid[i][j], i, j))
cells.sort()
def idx(r, c):
return r * n + c
processed = [[False] * n for _ in range(n)]
for elevation, r, c in cells:
processed[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 processed[nr][nc]:
uf.union(idx(r, c), idx(nr, nc))
if uf.connected(idx(0, 0), idx(n-1, n-1)):
return elevation
return -1 # should never reach
Time: for sorting. Space: .