Swim in Rising Water

You are given an n × n grid where grid[i][j] is the elevation of cell (i, j). Rain starts at time 0, and at time t the water everywhere is t deep. You can swim from a cell to one of its four neighbours when both cells have elevation at most t, and swimming takes no time. Starting at (0, 0), return the least time at which you can reach (n - 1, n - 1). This is LeetCode 778.

Limits: 1 <= n <= 50, and the values of grid are the numbers 0 to n2 - 1, each used exactly once.

The page gives two solutions. Solution 1 grows the reachable area from the cheapest edge outward with a min-heap, like Dijkstra. Solution 2 binary searches on the time and checks each guess with a BFS.

Example 1
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation: the target cell has elevation 3, so nothing earlier than time 3 can work, and at time 3 every cell is under water.
Example 2
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 route along the top row, down the right side to 16, then left and around the outer ring never goes above 16.
Example 3
Input: grid = [[3,2],[0,1]]
Output: 3
Explanation: you stand on (0, 0) from the start, so its own elevation 3 has to be under water first.

How to Think About It

Step 1: The cost of a path is its highest cell

Water only rises, so once a cell is under water it stays that way. A path from (0, 0) to the corner is usable at time t exactly when every cell on it has elevation at most t. The earliest time for one path is therefore the largest elevation on it, including both end cells.

Step 2: The answer is the best bottleneck

We want the path whose highest cell is as low as possible. A brute force tries t = 0, 1, 2 and so on and runs a flood fill each time. That is correct but costs up to n2 flood fills of n2 cells each.

Step 3: Dijkstra works with max instead of plus

Dijkstra's algorithm settles nodes in order of their best known cost. It only needs one property: extending a path never makes its cost smaller. With cost = highest elevation so far, stepping to a neighbour gives max(cost, grid[next]), which is never smaller.

So keep a min-heap of cells keyed by that cost. The first time a cell leaves the heap, no cheaper route to it exists, because every other route still in the heap already costs at least as much. When the corner leaves the heap, its cost is the answer. The same settling argument is explained in Dijkstra's Algorithm.

Another angle: guess the time and check it

If you can cross at time t, you can also cross at any later time, since the same path stays under water. A yes or no question that flips once from no to yes can be answered with binary search. For one guess t, a BFS that only steps on cells with elevation at most t tells you whether the corner is reachable. This is Solution 2, and the pattern is explained in Binary Search.

Walkthrough

Solution 1 on Example 2. Each row is one cell leaving the heap for the first time, with the cost it was settled at.

OrderCell settledElevationCost (time needed)
1 to 5(0, 0) to (0, 4), the top row0, 1, 2, 3, 40, 1, 2, 3, 4
6(1, 4)55
7(2, 4)1616
8 to 11(2, 3) to (2, 0), the middle row leftward15, 14, 13, 1216 each
12 to 13(3, 0), (4, 0)11, 1016 each
14 to 17(4, 1) to (4, 4), the bottom row rightward9, 8, 7, 616 each

After cost 5, the cheapest cells next to the settled area are 16 on the right and 21 to 24 in row 1, so the heap picks 16. From there every cell is lower than 16, and the cost stays 16 until the corner (4, 4) is settled. The answer is 16.

Solution 1: Min-Heap on the Highest Elevation

swimInWater runs Dijkstra from (0, 0), where the cost of a cell is the highest elevation on the best path to it, and stops when the corner is settled.

  • The starting cost: the heap starts with grid[0][0], not 0. In Example 3 the start has elevation 3, and the answer is 3 even though the rest of the grid is lower.
  • The new cost: Math.max(t, grid[nr][nc]) keeps the highest cell on the path. Adding elevations would answer a different question.
  • Skipping repeats: a cell can be pushed by several neighbours. The done check drops every entry after the first one polled, which is the cheapest.
  • Stopping early: the method returns when the corner is polled, not when it is pushed. A push only offers one route, while the poll proves no cheaper route is left. For n = 1 the start is the corner and the answer is grid[0][0], which is 0.

A common mistake is to push a neighbour with its own elevation, grid[nr][nc], instead of the maximum along the path. The heap then forgets the high cell it already crossed. On Example 2 that version returns 6, the elevation of the corner, instead of 16.

Java
import java.util.PriorityQueue;

public class SwimInRisingWater {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] done = new boolean[n][n];
        // {time needed to stand on this cell, row, col}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        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;               // a cheaper entry already settled this cell
            done[r][c] = true;
            if (r == n - 1 && c == n - 1) return t; // first poll of the corner is optimal
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !done[nr][nc]) {
                    // a path costs its highest cell
                    pq.add(new int[]{Math.max(t, grid[nr][nc]), nr, nc});
                }
            }
        }
        return -1; // not reached: every cell is connected to the corner
    }
}

Solution 2: Binary Search on Time with BFS

This version binary searches for the smallest time t at which a BFS over cells with elevation at most t reaches the corner.

  • The search range: the answer is at least the higher of the two end cells, since you must stand on both. It is at most n2 - 1, the highest value, when every cell is under water.
  • Why binary search is allowed: canReach(t) is false up to some time and true from then on. If it is true for mid, the answer is mid or earlier, so hi = mid; otherwise lo = mid + 1.
  • The BFS: it marks a cell as seen when it is added to the queue, so no cell is queued twice. It only enters a neighbour whose elevation is at most t.
  • The start cell: the BFS never tests grid[0][0]. That is safe only because lo already includes it.

On Example 2 the range starts at lo = 6, the corner's elevation, and hi = 24:

lohimidcanReach(mid)
62415false
162420true
162018true
161817true
161716true

The range closes at 16, matching Solution 1. A common mistake is to start the search at lo = 0 while the BFS still skips the start cell. Example 3 then returns 1, because the low cells 0 and 1 form a path while (0, 0) itself is still dry at elevation 3.

Java
import java.util.ArrayDeque;
import java.util.Deque;

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

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int lo = Math.max(grid[0][0], grid[n - 1][n - 1]); // both ends must be under water
        int hi = n * n - 1;                                // every cell is under water by then
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canReach(grid, mid)) {
                hi = mid;      // mid works, so the answer is mid or earlier
            } else {
                lo = mid + 1;  // mid is too early
            }
        }
        return lo;
    }

    // BFS over cells whose elevation is at most t.
    private boolean canReach(int[][] grid, int t) {
        int n = grid.length;
        boolean[][] seen = new boolean[n][n];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, 0});
        seen[0][0] = true;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            if (cell[0] == n - 1 && cell[1] == n - 1) return true;
            for (int[] d : DIRS) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                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

  • Solution 1 time: O(n2 log n). Each of the n2 cells is settled once and pushes at most 4 entries, so the heap sees O(n2) operations. Each costs log(n2) = 2 log n.
  • Solution 1 space: O(n2). The done array has one flag per cell, and the heap can hold up to four entries per cell before the stale ones are polled.
  • Solution 2 time: O(n2 log n). The search range has at most n2 values, so there are about log(n2) = 2 log n rounds. Each round runs one BFS that touches every cell at most once.
  • Solution 2 space: O(n2). Each BFS allocates a fresh seen grid of n2 flags, and its queue can hold a large share of the cells at once.

Which One to Use

Both solutions run in O(n2 log n) and return the same answers, and for n <= 50 either one is instant. Solution 1 is one pass and often stops early, as soon as the corner is settled. Solution 2 repeats a plain BFS about a dozen times, but each piece is simple and easy to test on its own. Choose Solution 1 when you recognise a "minimise the worst step" path problem. Choose Solution 2 when checking a single guess is easy and the answers are monotonic, as in Koko Eating Bananas.

Spreading through a height grid from the edges, without a clock, is Pacific Atlantic Water Flow.