Swim in Rising Water

The problem

Implement `swimInWater(grid)` where `grid[i][j]` is a distinct elevation in `[0, n^2)`. At time `t` the water level is `t`, and a swim between two adjacent cells is only possible once both cells' elevations are `<= t`. Return the minimum `t` at which `(0,0)` can reach `(n-1,n-1)`.

`grid = [[0,1],[2,3]]` returns `3` — no path exists at `t = 2`, since `(1,1)`'s elevation `3` is still above water, so `t` has to rise to `3` before every cell on the only path (`0 -> 1 -> 3` or `0 -> 2 -> 3`) is submerged.

The approach

Same idea as `minCostConnectPoints`: sort a list built from the grid, then let union-find (the same `find`/path compression as every earlier DSU entry) decide connectivity as that sorted list gets walked. What differs is what gets sorted and unioned — `minCostConnectPoints` sorted *edges* between fixed nodes; this sorts *cells* themselves and only unions a cell with a neighbour once both are 'active', meaning their elevation is `<= ` the current threshold.

A cell only unions with its 4-directional neighbours once it's marked active. Processing cells in ascending elevation order guarantees that by the time `(r, c)` is reached, every already-active neighbour has an elevation `<= grid[r][c]` and can be unioned immediately; a neighbour with a higher elevation simply isn't active yet and gets skipped until its own turn comes up.

Because `grid` uses every value from `0` to `n^2 - 1` exactly once, processing cells in elevation order is the same as sweeping `t` upward one submerged cell at a time. So instead of binary-searching for `t` and re-checking connectivity at each guess, the loop checks `find(start) === find(end)` right after each activation and returns that cell's own elevation the moment it's true — necessarily the smallest `t` at which the corners connect.

The solution

class Solution {
    /**
     * @param {number[][]} grid
     * @return {number}
     */
    swimInWater(grid) {
        const n = grid.length;
        const parent = Array.from({ length: n * n }, (_, i) => i);

        const find = (x) => {
            while (parent[x] !== x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };

        const cells = [];
        for (let row = 0; row < n; row++) {
            for (let col = 0; col < n; col++) {
                cells.push([grid[row][col], row, col]);
            }
        }
        cells.sort((a, b) => a[0] - b[0]);

        const active = Array.from({ length: n }, () => new Array(n).fill(false));
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

        for (const [elevation, row, col] of cells) {
            active[row][col] = true;
            const id = row * n + col;

            for (const [dr, dc] of directions) {
                const newRow = row + dr;
                const newCol = col + dc;
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && active[newRow][newCol]) {
                    const neighbourId = newRow * n + newCol;
                    const rootA = find(id);
                    const rootB = find(neighbourId);
                    if (rootA !== rootB) parent[rootA] = rootB;
                }
            }

            if (find(0) === find(n * n - 1)) return elevation;
        }

        return n * n - 1;
    }
}

Time O(n^2 log n)Space O(n^2)