96.Swim in Rising Water

HardGraphs · 17/19

Problem

You are given an n x n grid where grid[i][j] is the elevation at cell (i, j). Rain starts falling, and at time t the water level everywhere is t. You can swim from a cell to a 4-directionally adjacent cell if both cells have elevation at most t; swimming itself takes no time.

Starting at (0, 0), return the least time t at which you can reach the bottom-right cell (n - 1, n - 1).

Examples

Input:  grid = [[0,2],
                [1,3]]
Output: 3
Explanation: (1,1) has elevation 3, so you must wait until t = 3 no matter which path you take.

Input:  grid = [[0,1,2,3,4],
                [24,23,22,21,5],
                [12,13,14,15,16],
                [11,17,18,19,20],
                [10,9,8,7,6]]
Output: 16
Explanation: The best path snakes 0-1-2-3-4-5-16-15-14-13-12-11-10-9-8-7-6; its highest cell is 16.

Constraints

n == grid.length == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n²
Every value grid[i][j] is unique.

💡 Key Insight

The time needed for a path equals the maximum elevation on that path, so we want the path that minimises its maximum cell (a minimax / "bottleneck" path). Dijkstra works with a modified cost: instead of summing weights, the cost of reaching a neighbour is max(costSoFar, elevation). Because this cost never decreases along a path, the first time the heap pops (n-1, n-1) its cost is optimal.

Brute Force — Try Every Time

TimeO(n⁴)SpaceO(n²)

Intuition

For a fixed t, the question "can I reach the corner?" is a simple flood fill over cells with elevation <= t. Try t = grid[0][0], grid[0][0] + 1, ... and return the first t for which the corner is reachable.

Algorithm

For t from grid[0][0] up to n² - 1:
Run DFS from (0, 0) visiting only cells with grid <= t.
If DFS reaches (n - 1, n - 1), return t.

Visualization

grid = [[0,2],[1,3]]

t=0: reachable {(0,0)}                 corner? no
t=1: reachable {(0,0),(1,0)}           no
t=2: reachable {(0,0),(1,0),(0,1)}     no
t=3: corner (1,1) now open             yes -> 3

Code

java

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        for (int t = grid[0][0]; ; t++) {
            if (canReach(grid, 0, 0, t, new boolean[n][n])) {
                return t;
            }
        }
    }

    private boolean canReach(int[][] grid, int r, int c, int t, boolean[][] seen) {
        int n = grid.length;
        if (r == n - 1 && c == n - 1) {
            return true;
        }
        seen[r][c] = true;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) {
                if (canReach(grid, nr, nc, t, seen)) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity

Time: O(n⁴) — up to n² values of t, each with an O(n²) flood fill.
Space: O(n²) — visited grid and recursion stack.

Binary Search on Time + DFS

TimeO(n² log n)SpaceO(n²)

Intuition

Reachability is monotonic in t: if the corner is reachable at time t, it is reachable at every later time. So instead of trying every t, binary search for the smallest feasible one in the range [grid[0][0], n² - 1].

Algorithm

lo = grid[0][0], hi = n² - 1.
While lo < hi: mid = (lo + hi) / 2; if the corner is reachable at mid, set hi = mid, else lo = mid + 1.
Return lo.

Visualization

5x5 example, range [0, 24]
mid=12 -> blocked (path needs 16)        lo=13
mid=18 -> reachable                      hi=18
mid=15 -> blocked                        lo=16
mid=17 -> reachable                      hi=17
mid=16 -> reachable                      hi=16   lo == hi -> 16

Code

java

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int lo = grid[0][0], hi = n * n - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canReach(grid, 0, 0, mid, new boolean[n][n])) {
                hi = mid; // feasible: try an earlier time
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private boolean canReach(int[][] grid, int r, int c, int t, boolean[][] seen) {
        int n = grid.length;
        if (r == n - 1 && c == n - 1) {
            return true;
        }
        seen[r][c] = true;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) {
                if (canReach(grid, nr, nc, t, seen)) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity

Time: O(n² log n) — log(n²) binary-search steps, each an O(n²) flood fill.
Space: O(n²) — visited grid and recursion stack.

Dijkstra with Max-CostOptimal

TimeO(n² log n)SpaceO(n²)

Intuition

Run Dijkstra where a cell's "distance" is the highest elevation seen on the best path to it. Pop the cell with the smallest such value; moving to a neighbour costs max(current, grid[neighbour]). The heap always expands the lowest reachable water level first, so when the bottom-right cell is popped we have the minimum possible bottleneck. Every cell is finalised once, and we can stop as soon as the target is popped.

Algorithm

Push (grid[0][0], 0, 0) into a min-heap; mark (0, 0) visited.
Pop (time, r, c). If it is the target, return time.
For each unvisited neighbour, mark it and push (max(time, grid[nr][nc]), nr, nc).

Dry Run

flowchart LR
    A["(0,0) elev 0<br/>cost 0"] -->|"max(0,2) = 2"| B["(0,1) elev 2<br/>cost 2"]
    A -->|"max(0,1) = 1"| C["(1,0) elev 1<br/>cost 1"]
    C -->|"max(1,3) = 3"| D["(1,1) elev 3<br/>cost 3"]
    B -->|"max(2,3) = 3"| D

heap: (0,(0,0))
pop (0,(0,0)) push (1,(1,0)) (2,(0,1))
pop (1,(1,0)) push (3,(1,1))
pop (2,(0,1)) (1,1) already queued
pop (3,(1,1)) target -> return 3

Code

java

import java.util.PriorityQueue;

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] visited = new boolean[n][n];
        // heap of {timeNeeded, row, col}, smallest time first
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[] {grid[0][0], 0, 0});
        visited[0][0] = true;

        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int time = top[0], r = top[1], c = top[2];
            if (r == n - 1 && c == n - 1) {
                return time; // first pop of the target is optimal
            }
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr][nc]) {
                    continue;
                }
                visited[nr][nc] = true;
                // the path's cost is its highest elevation so far
                heap.offer(new int[] {Math.max(time, grid[nr][nc]), nr, nc});
            }
        }
        return -1; // unreachable for valid input
    }
}

Complexity

Time: O(n² log n) — each of the n² cells enters the heap once.
Space: O(n²) — heap and visited grid.

Complexity Comparison

Approach	Time	Space
Brute Force — Try Every Time	O(n⁴)	O(n²)
Binary Search + DFS	O(n² log n)	O(n²)
Dijkstra with Max-Cost	O(n² log n)	O(n²)

Common Pitfalls

Summing elevations along the path — the cost is the maximum elevation, not the total.
Starting the search at t = 0 and forgetting that grid[0][0] itself may be high; the answer is at least grid[0][0] (and at least grid[n-1][n-1]).
Marking cells visited on pop vs. push: marking on push is safe here only because a cell's cost max(time, elev) from the earliest-popped parent is already minimal; be consistent.
Recursion depth: a DFS over 2500 cells is fine, but much larger grids would need an iterative flood fill.