Process cells in order of increasing elevation. At each step, union the cell with its neighbors (if they're already processed):
function swimInWater(grid):
n = grid.length
uf = new UnionFind(n * n)
// Sort cells by elevation
cells = []
for i from 0 to n-1:
for j from 0 to n-1:
cells.add((grid[i][j], i, j))
sort(cells)
function idx(r, c):
return r * n + c
processed = n x n grid of false
for each (elevation, r, c) in cells:
processed[r][c] = true
for each (dr, dc) in [(0,1),(0,-1),(1,0),(-1,0)]:
nr = r + dr
nc = 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: .