LeetCode 778 Swim in Rising Water - Implementation

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

$O(n^2 \log n)$ time, $O(n^2)$ space.