Swim in Rising Water

Hard · Advanced Graphs · Explanation and code example

Kruskal's Algorithm

How it works

Water level t rises over time. At time t, you’re allowed to step only on cells with height <= t.
So as t increases, more cells become “open” and neighboring open cells form bigger connected regions.

We want the earliest time t when the start cell (0,0) and end cell (N-1,N-1) become part of the same connected component.

DSU (Union-Find) is perfect for this: it quickly merges neighboring open cells and checks if start and end are connected.

Steps

  1. Create a list of all cells as (height, r, c) and sort by height (smallest first).
  2. Initialize dsu for N*N cells (each cell is a node with id = r*N + c).
  3. Process cells in increasing height order:
    • Current cell (r,c) becomes "open" at time t = height.
    • For each of its 4 neighbors:
      • If the neighbor's height <= t, it is already open (or also open now), so union the two cells.
    • After unions, check if start (0) and end (N*N-1) are connected.
    • The first t where they connect is the answer.
  4. Return that t.

Complexity

  • Time complexity: O(n ^ 2 log n)
  • Space complexity: O(n ^ 2)

Things to watch for

Confusing Time with Step Count

A common mistake is treating "time" as the number of steps taken. In this problem, time represents the maximum height you must wait for the water to rise to before you can traverse your chosen path. It is not the path length.

Forgetting to Include Start and End Cells

When calculating the minimum time, you must include both grid[0][0] and grid[n-1][n-1] in your considerations. The answer is at least max(grid[0][0], grid[n-1][n-1]) since you must be able to stand on both endpoints.

Incorrect Binary Search Bounds

When using binary search, setting the wrong initial bounds can cause issues. The lower bound should be the minimum value in the grid (or at least grid[0][0]), and the upper bound should be the maximum value. Using 0 to n*n-1 works but is less precise.

Not Resetting Visited Array Between Searches

In both the linear search and binary search DFS approaches, forgetting to reset the visited array between different attempts (for different time values) leads to incorrect results. Each DFS with a new threshold needs a fresh visited state.

Union-Find: Incorrect Node Indexing

When using Kruskal's algorithm with DSU, a frequent bug is incorrectly converting 2D coordinates to 1D indices. The formula r * N + c must be used consistently, and you must ensure neighbors are already "open" (have height <= current time) before attempting to union them.

Python code example

from typing import List

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True

    def connected(self, u, v):
        return self.find(u) == self.find(v)

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N = len(grid)
        dsu = DSU(N * N)
        positions = sorted((grid[r][c], r, c) for r in range(N) for c in range(N))
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        for t, r, c in positions:
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < N and grid[nr][nc] <= t:
                    dsu.union(r * N + c, nr * N + nc)
            if dsu.connected(0, N * N - 1):
                return t

C++ code example

class DSU {
    vector<int> Parent, Size;
public:
    DSU(int n) : Parent(n + 1), Size(n + 1, 1) {
        for (int i = 0; i <= n; i++) Parent[i] = i;
    }

    int find(int node) {
        if (Parent[node] != node)
            Parent[node] = find(Parent[node]);
        return Parent[node];
    }

    bool unionSets(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;
        if (Size[pu] < Size[pv]) swap(pu, pv);
        Size[pu] += Size[pv];
        Parent[pv] = pu;
        return true;
    }

    bool connected(int u, int v) {
        return find(u) == find(v);
    }
};

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int N = grid.size();
        DSU dsu(N * N);
        vector<tuple<int, int, int>> positions;
        for (int r = 0; r < N; r++)
            for (int c = 0; c < N; c++)
                positions.emplace_back(grid[r][c], r, c);

        sort(positions.begin(), positions.end());
        vector<pair<int, int>> directions = {
            {0, 1}, {1, 0}, {0, -1}, {-1, 0}
        };

        for (auto& [t, r, c] : positions) {
            for (auto& [dr, dc] : directions) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < N && nc >= 0 &&
                    nc < N && grid[nr][nc] <= t) {
                    dsu.unionSets(r * N + c, nr * N + nc);
                }
            }
            if (dsu.connected(0, N * N - 1)) return t;
        }
        return N * N;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations