#778 Swim in Rising Water

frequently reported atMeta Google Amazon

the problem

In plain words

grid is n × n, grid[r][c] is the elevation, and all values are a permutation of 0..n² − 1. At time t the water depth everywhere is t, and you can swim between adjacent cells whose elevations are both ≤ t. Return the least t at which you can swim from the top-left to the bottom-right.

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

out 3

You can't reach the corner until it is underwater at t = 3.

in 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]]

out 16

1 ≤ n ≤ 50
0 ≤ grid[i][j] < n²
All values are unique

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternDijkstra Binary search on the answer Union-Find (DSU)

The time needed for a path is its highest cell. We want the path whose highest cell is as low as possible — a minimax path, exactly like LC 1631.

solutions

From brute force to optimal

For a guess t, DFS through cells ≤ t. The smallest t that reaches the corner is the answer.

lo = grid[0][0], hi = n² − 1.
DFS from (0,0) using cells ≤ mid.
Shrink the range until lo == hi.

timeO(n² · log n)

log(n²) = 2 log n guesses, each O(n²).

spaceO(n²)

visited grid and DFS recursion (up to n² deep).

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3 4    public int swimInWater(int[][] grid) {5        int n = grid.length;6        int lo = grid[0][0], hi = n * n - 1;            // answer is at least the start cell7        while (lo < hi) {8            int mid = lo + (hi - lo) / 2;9            if (reach(grid, 0, 0, mid, new boolean[n][n])) hi = mid;10            else lo = mid + 1;11        }12        return lo;13    }14 15    /** Can we reach the corner using only cells with elevation ≤ t? */16    private boolean reach(int[][] g, int r, int c, int t, boolean[][] seen) {17        int n = g.length;18        if (r < 0 || c < 0 || r >= n || c >= n || seen[r][c] || g[r][c] > t) return false;19        if (r == n - 1 && c == n - 1) return true;20        seen[r][c] = true;21        for (int[] d : DIRS) if (reach(g, r + d[0], c + d[1], t, seen)) return true;22        return false;23    }24}

Always swim into the lowest reachable cell next. Track the highest elevation seen on the way; when the corner pops, that's the answer.

Heap of {max elevation so far, r, c}, start {grid[0][0], 0, 0}.
Poll; if it's the corner, return its value.
Push unseen neighbours with max(t, grid[nr][nc]); mark them seen.

timeO(n² · log n)

n² cells pushed once each; heap ops O(log n²) = O(log n).

spaceO(n²)

seen grid and heap.

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3 4    public int swimInWater(int[][] grid) {5        int n = grid.length;6        boolean[][] seen = new boolean[n][n];7        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));8        pq.offer(new int[] {grid[0][0], 0, 0});          // {highest cell on the path, row, col}9        seen[0][0] = true;10        while (!pq.isEmpty()) {11            int[] top = pq.poll();12            int t = top[0], r = top[1], c = top[2];13            if (r == n - 1 && c == n - 1) return t;14            for (int[] d : DIRS) {15                int nr = r + d[0], nc = c + d[1];16                if (nr < 0 || nc < 0 || nr >= n || nc >= n || seen[nr][nc]) continue;17                seen[nr][nc] = true;                      // first push is already the best (minimax)18                pq.offer(new int[] {Math.max(t, grid[nr][nc]), nr, nc});19            }20        }21        return -1;22    }23}

Flip the question: flood cells in order of elevation. Because elevations are a permutation, the cell with value t floods exactly at time t. Union it with already-flooded neighbours; the first t at which the corners share a root is the answer.

cellAt[value] = cell (no sorting needed).
For t = 0, 1, …: union cellAt[t] with neighbours ≤ t.
Return the first t where find(start) == find(end).

timeO(n² · α(n²))

n² cells, ≤ 4 unions each, and no sort thanks to the permutation. Union by size + path compression make each find/union near O(1) — slightly better than the heap's log factor.

spaceO(n²)

parent, size and cellAt arrays.

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3 4    private int[] parent, size;5 6    private int find(int x) {7        if (parent[x] != x) parent[x] = find(parent[x]);8        return parent[x];9    }10 11    private void union(int a, int b) {12        int ra = find(a), rb = find(b);13        if (ra == rb) return;14        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }15        parent[rb] = ra; // smaller pool hangs under the bigger one16        size[ra] += size[rb];17    }18 19    public int swimInWater(int[][] grid) {20        int n = grid.length;21        int[] cellAt = new int[n * n]; // values are a permutation of 0..n²−1: no sort needed22        for (int r = 0; r < n; r++)23            for (int c = 0; c < n; c++) cellAt[grid[r][c]] = r * n + c;24        parent = new int[n * n];25        size = new int[n * n];26        for (int i = 0; i < n * n; i++) { parent[i] = i; size[i] = 1; }27        for (int t = 0; t < n * n; t++) { // water rises to level t28            int r = cellAt[t] / n, c = cellAt[t] % n; // the cell that just went under29            for (int[] d : DIRS) {30                int nr = r + d[0], nc = c + d[1];31                if (nr < 0 || nc < 0 || nr >= n || nc >= n || grid[nr][nc] > t) continue;32                union(r * n + c, nr * n + nc); // join flooded neighbours33            }34            if (find(0) == find(n * n - 1)) return t; // corner to corner by water35        }36        return n * n - 1;37    }38}

sim

Flooding dry run

loading simulation…

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3 4    private int[] parent, size;5 6    private int find(int x) {7        if (parent[x] != x) parent[x] = find(parent[x]);8        return parent[x];9    }10 11    private void union(int a, int b) {12        int ra = find(a), rb = find(b);13        if (ra == rb) return;14        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }15        parent[rb] = ra; // smaller pool hangs under the bigger one16        size[ra] += size[rb];17    }18 19    public int swimInWater(int[][] grid) {20        int n = grid.length;21        int[] cellAt = new int[n * n]; // values are a permutation of 0..n²−1: no sort needed22        for (int r = 0; r < n; r++)23            for (int c = 0; c < n; c++) cellAt[grid[r][c]] = r * n + c;24        parent = new int[n * n];25        size = new int[n * n];26        for (int i = 0; i < n * n; i++) { parent[i] = i; size[i] = 1; }27        for (int t = 0; t < n * n; t++) { // water rises to level t28            int r = cellAt[t] / n, c = cellAt[t] % n; // the cell that just went under29            for (int[] d : DIRS) {30                int nr = r + d[0], nc = c + d[1];31                if (nr < 0 || nc < 0 || nr >= n || nc >= n || grid[nr][nc] > t) continue;32                union(r * n + c, nr * n + nc); // join flooded neighbours33            }34            if (find(0) == find(n * n - 1)) return t; // corner to corner by water35        }36        return n * n - 1;37    }38}

in the room

How to say it in the interview

talk track

Name the pattern: "minimise the maximum along a path."
Mention all three approaches; code the heap; note the union-find trick uses the permutation guarantee (no sort needed).

traps

Forgetting that the start cell's own elevation counts: the answer is at least grid[0][0].
Summing elevations instead of taking the max along the path.

what they ask next

Follow-ups

Why is marking seen on push safe here?

The heap pops in increasing max-height order, so the first push of a cell already carries the smallest possible max — later pushes can only be higher.

Path With Minimum Effort (LC 1631, above)?

Same minimax idea, but the cost is the biggest height difference between steps: run the same heap, or union-find over edges sorted by difference (Kruskal-style).

before you submit

Edge cases to test

1 × 1 grid → grid[0][0], which is 0.
The start cell can be the highest on the best route ([[3,2],[0,1]] → 3): the answer is at least grid[0][0].
The best route may wind around a peak instead of going straight.

practise next