☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

Swim in Rising Water

Medium TUF ID 1006 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n x n grid where grid[r][c] is the elevation of that cell. It starts raining, and at time t the water level everywhere is t. You can move from a cell to a 4-directionally adjacent cell only if both elevations are at most t, and swimming any distance takes no time. Starting at (0, 0), return the least time t at which you can reach (n - 1, n - 1).

Constraints: 1 ≤ n ≤ 50, and the elevations are a permutation of 0 .. n^2 - 1 (all distinct).

Example 1

grid = [[0,2],
        [1,3]]
answer = 3          // the destination itself has elevation 3, so nothing below t = 3 works

Example 2

grid = [[0,6,1],
        [7,8,2],
        [3,4,5]]
answer = 6          // path 0 -> 6 -> 1 -> 2 -> 5 has highest cell 6; going down the left costs 7

Reframing the problem

At time t, exactly the cells with elevation ≤ t are usable. A path works at time t if and only if every cell on it, including both corners, has elevation ≤ t. So the time a path needs is the maximum elevation along it, and the answer is

min over all paths of (max elevation on the path).

This is a bottleneck (minimax) path problem. Three classic tools solve it, and each gives one of the approaches below: binary search on the answer, Dijkstra with “max” in place of “+”, and Kruskal-style union in increasing order.

Approach 1: Binary search on the time, BFS to check

Intuition. Feasibility is monotone in t: if you can reach the corner at time t, you can at any later time, because the water only rises and more cells become usable. Monotone yes/no questions are what binary search on the answer is for. For a candidate t, a plain BFS over cells with elevation ≤ t tells us whether the destination is reachable.

The search range starts at grid[0][0] (you cannot even stand at the start before that) and ends at the maximum elevation (at that time every cell is open, so the answer is surely feasible).

Algorithm.

  1. lo = grid[0][0], hi = max elevation.
  2. While lo < hi: mid = lo + (hi - lo) / 2. If canReach(mid), set hi = mid; otherwise lo = mid + 1.
  3. Return lo.
  4. canReach(t) runs BFS from (0, 0) stepping only onto cells with elevation ≤ t.
static int binarySearchBfs(int[][] grid) {
    int lo = grid[0][0], hi = 0;
    for (int[] row : grid) for (int v : row) hi = Math.max(hi, v);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canReach(grid, mid)) hi = mid;               // mid works, so the answer is mid or smaller
        else lo = mid + 1;
    }
    return lo;
}

static boolean canReach(int[][] grid, int t) {
    int n = grid.length;
    if (grid[0][0] > t) return false;
    boolean[][] seen = new boolean[n][n];
    Deque<int[]> queue = new ArrayDeque<>();
    seen[0][0] = true;
    queue.add(new int[]{0, 0});
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        if (cell[0] == n - 1 && cell[1] == n - 1) return true;
        for (int k = 0; k < 4; k++) {
            int nr = cell[0] + DR[k], nc = cell[1] + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) {
                seen[nr][nc] = true;
                queue.add(new int[]{nr, nc});
            }
        }
    }
    return false;
}

Complexity. Time O(n^2 · log(n^2)): about log2(n^2) BFS runs, each O(n^2). Space O(n^2) for the seen array and the queue.

Approach 2: Dijkstra on the bottleneck cost

Intuition. Define best(cell) as the least time needed to reach that cell. Moving from a cell reached at time t into a neighbour of elevation h costs max(t, h): you need the water to cover both what you already crossed and the new cell. This cost never decreases along a path, which is the property that makes Dijkstra’s greedy choice valid. The cell with the smallest tentative time in the priority queue can never be improved by going through cells with larger times, because max can only keep or raise the value.

So run Dijkstra from (0, 0) with initial value grid[0][0], using max instead of addition, and stop the first time (n - 1, n - 1) is popped.

Algorithm.

  1. Push {grid[0][0], 0, 0} into a min-heap ordered by time.
  2. Pop the smallest entry. Skip it if its cell is already finalised. Otherwise finalise it; if it is the destination, return its time.
  3. For each neighbour not yet finalised, push {max(time, grid[nr][nc]), nr, nc}.
static int dijkstra(int[][] grid) {
    int n = grid.length;
    boolean[][] done = new boolean[n][n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));   // {time, r, c}
    pq.add(new int[]{grid[0][0], 0, 0});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int t = top[0], r = top[1], c = top[2];
        if (done[r][c]) continue;                        // stale entry
        done[r][c] = true;
        if (r == n - 1 && c == n - 1) return t;
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !done[nr][nc]) {
                pq.add(new int[]{Math.max(t, grid[nr][nc]), nr, nc});
            }
        }
    }
    return -1;                                           // unreachable for a non-empty grid
}

Complexity. Time O(n^2 log n): each cell is pushed at most four times, so the heap holds O(n^2) entries and each operation costs O(log n^2) = O(log n). Space O(n^2) for the heap and the done array.

Approach 3: Disjoint Set, let the water rise

Intuition. Simulate the rain directly. Sort the cells by elevation and “open” them one at a time in that order. Opening a cell means the water has reached it, so union it with each neighbour that is already open. The first moment (0, 0) and (n - 1, n - 1) are in the same set, a path of open cells joins them. Every cell opened so far has elevation at most the current one, so the current cell’s elevation is a sufficient time. It is also the least: one step earlier, the corners were in different sets, so no path of lower cells existed.

This is Kruskal’s algorithm in disguise. Processing edges in increasing weight and stopping when two vertices connect yields the minimum bottleneck path, because a minimum spanning tree also minimises the maximum edge on the path between any two vertices.

static final class DisjointSet {
    final int[] parent, size;

    DisjointSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                         // already in the same set
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;                                    // hang the smaller tree under the larger
        size[ra] += size[rb];
        return true;
    }
}

Algorithm.

  1. Sort the cell ids r * n + c by elevation.
  2. For each id in that order: mark it open, union it with each open neighbour.
  3. If find(0) == find(n * n - 1), return the elevation of the cell just opened.
static int unionFind(int[][] grid) {
    int n = grid.length, cells = n * n;
    Integer[] order = new Integer[cells];
    for (int i = 0; i < cells; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(grid[a / n][a % n], grid[b / n][b % n]));
    DisjointSet ds = new DisjointSet(cells);
    boolean[][] open = new boolean[n][n];
    for (int id : order) {
        int r = id / n, c = id % n;
        open[r][c] = true;                               // water level has reached this cell
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && open[nr][nc]) ds.union(id, nr * n + nc);
        }
        if (ds.find(0) == ds.find(cells - 1)) return grid[r][c];
    }
    return -1;
}

Dry run on example 2:

opened (elevation) unions with open neighbours corners connected?
(0,0) 0 none no
(0,2) 1 none no
(1,2) 2 (0,2) no
(2,0) 3 none no
(2,1) 4 (2,0) no
(2,2) 5 (1,2), (2,1) no: the right and bottom edges are one set, but (0,0) is alone
(0,1) 6 (0,0), (0,2) yes, return 6

Complexity. Time O(n^2 log n) for the sort; the unions add only O(n^2 · α(n^2)). Because the elevations are a permutation of 0 .. n^2 - 1, the sort can be replaced by an array position[value] = id, making the whole method O(n^2 · α(n^2)). Space O(n^2).

Which approach to use

All three are fast for n ≤ 50. Binary search is the most reusable pattern when you can only check a candidate answer. Dijkstra generalises to graphs where you need the bottleneck from one source to every cell. The Disjoint Set version is the shortest to reason about once you see it as “water rising” and is the one this section of the sheet is about.

Edge cases and pitfalls