Swim in Rising Water LeetCode 778 Guide

LeetCode 778 — Swim in Rising Water — gives you an n x n grid where grid[i][j] represents the elevation at cell (i, j). At time t, the water level is t, and you can swim through any cell with elevation <= t. Find the minimum time to swim from (0, 0) to (n-1, n-1).

You can move in four directions at each step. You must wait until the water rises high enough to enter a cell. The minimum time is the maximum elevation encountered on the optimal path — the path that minimizes this maximum.

This is a minimax path problem: find the path from source to destination that minimizes the maximum edge weight (here, cell elevation). It can be solved with modified Dijkstra, binary search + BFS, or Union-Find processing cells in elevation order.

Use a min-heap with entries (maxElevation, row, col). Start with (grid[0][0], 0, 0). Pop the entry with the smallest max elevation. If it is the destination, return the max elevation. Otherwise, explore four neighbors.

For each neighbor (nr, nc), the new max elevation is max(currentMax, grid[nr][nc]). If this is less than the best known max for (nr, nc), push it to the heap. Use a visited array or best-known-max array to avoid reprocessing.

This is Dijkstra where the "distance" is the max elevation on the path rather than the sum. The min-heap ensures we always process the path with the smallest max elevation first. When (n-1, n-1) is first popped, its max elevation is optimal.

Binary search on the answer T in range [max(grid[0][0], grid[n-1][n-1]), n*n - 1]. For each candidate T, run a BFS/DFS from (0, 0) using only cells with elevation <= T. If (n-1, n-1) is reachable, T is feasible — search lower. Otherwise search higher.

The lower bound is max(grid[0][0], grid[n-1][n-1]) because the path must include both endpoints. The upper bound is the maximum elevation in the grid (n*n - 1). Binary search runs O(log(n^2)) = O(2 log n) iterations.

Each BFS iteration takes O(n^2) time (visiting all cells). Total: O(n^2 * log(n^2)) = O(n^2 * 2 log n) = O(n^2 log n). This matches the Dijkstra approach in asymptotic complexity but with a larger constant factor.

Sort all cells by elevation. Process them in increasing order. For each cell, union it with any adjacent cells that have already been processed (lower or equal elevation). After each union, check if (0, 0) and (n-1, n-1) are connected.

The first time they become connected, the current cell's elevation is the answer — it is the maximum elevation on the path that just became feasible. This is essentially Kruskal's algorithm adapted for grid connectivity.

Time complexity is O(n^2 * alpha(n^2)) ≈ O(n^2) for the Union-Find operations, plus O(n^2 log(n^2)) for sorting. The sorting dominates, giving O(n^2 log n) overall — same as the other approaches.

Consider grid = [[0,2],[1,3]]. Dijkstra: heap = [(0, 0, 0)]. Pop (0, 0, 0). Neighbors: (0,1) with max(0,2)=2, (1,0) with max(0,1)=1. Push both. Heap: [(1, 1, 0), (2, 0, 1)].

Pop (1, 1, 0). Not destination. Neighbor (1,1) with max(1,3)=3. Neighbor (0,0) already visited. Push (3, 1, 1). Heap: [(2, 0, 1), (3, 1, 1)]. Pop (2, 0, 1). Neighbor (1,1) with max(2,3)=3 — already have 3, no improvement. Heap: [(3, 1, 1)].

Pop (3, 1, 1). This is the destination! Return 3. The optimal path is (0,0)→(1,0)→(1,1) with max elevation 3. At time 3, water level is 3, all cells on this path have elevation <= 3.

Python Dijkstra: import heapq. heap = [(grid[0][0], 0, 0)]. visited = set(). While heap: maxElev, r, c = heappop(heap). If (r,c) == (n-1,n-1): return maxElev. If (r,c) in visited: continue. visited.add((r,c)). For each neighbor: heappush(heap, (max(maxElev, grid[nr][nc]), nr, nc)).

Python binary search: lo, hi = max(grid[0][0], grid[-1][-1]), n*n-1. While lo < hi: mid = (lo+hi)//2. BFS from (0,0) using cells <= mid. If reaches (n-1,n-1): hi = mid. Else: lo = mid + 1. Return lo.

Java uses PriorityQueue<int[]> for Dijkstra with a comparator on the first element. The BFS approach uses a Queue<int[]> with boolean[][] visited. Both are clean implementations under 30 lines.

Dijkstra: O(n^2 log n). The heap holds at most n^2 entries. Each cell is processed once. Each heap operation is O(log(n^2)) = O(log n). Total: n^2 cells * O(log n) = O(n^2 log n).

Binary search + BFS: O(n^2 log n). Binary search runs O(log(n^2)) iterations. Each BFS is O(n^2). Total: O(n^2 * log(n^2)) = O(n^2 * 2 log n) = O(n^2 log n).

Space: O(n^2) for all approaches — the visited set/array and heap/queue. With n <= 50 (the constraint), n^2 = 2500, so all approaches are fast.

Path With Minimum Effort (LeetCode 1631) is nearly identical: minimize the maximum absolute difference between adjacent cells on a path. The Dijkstra and binary search approaches transfer directly. Practice both problems together.

Cheapest Flights Within K Stops (LeetCode 787) uses modified Dijkstra with a different constraint (stop limit instead of minimax). Both problems show how to adapt Dijkstra's framework to non-standard objectives.

Trapping Rain Water II (LeetCode 407) uses a similar min-heap on a 2D grid but computes water volume rather than finding a path. The heap processes cells by elevation from the boundary inward. The structural similarity to Swim in Rising Water makes them natural companions.