Swim in Rising Water LeetCode 778 Guide

LeetCode 778 Swim in Rising Water presents an n x n grid where grid[i][j] is the elevation at cell (i, j). All elevations are a permutation of 0 to n*n-1, so every cell has a unique height. At time t, the water level rises to t: you can swim from one cell to an adjacent cell (up, down, left, right) if and only if both cells have elevation at most t. You start at (0, 0) and want to reach (n-1, n-1).

The goal is to find the minimum time t such that there exists a path from (0, 0) to (n-1, n-1) where every cell along the path has elevation at most t. Because water must rise to cover both the cell you are leaving and the cell you are entering, the bottleneck of any path is the maximum elevation along it. You want to choose the path that minimizes this maximum elevation.

The answer is always at least max(grid[0][0], grid[n-1][n-1]) because you must wait until water covers both the start and the destination before you can swim at all. For a 1x1 grid the answer is grid[0][0]. For larger grids the answer is determined by the most constrained cell on the optimal route through the grid.

The key insight is that the cost of using a path is determined not by the sum of elevations along it but by the maximum elevation among all cells on the path. You want the path from (0,0) to (n-1,n-1) that minimizes this maximum. This is called the minimax path problem: minimize the maximum edge (or node) weight along a path between two vertices in a graph.

Translating into graph terms: model each grid cell as a node, and each adjacency as an edge whose weight is the maximum of the two endpoint elevations. Then the answer is the minimum over all paths of the maximum edge weight on that path. Equivalently, think of each node having a cost equal to its elevation, and the path cost is the maximum node cost seen. Both formulations are equivalent and solved by the same algorithms.

Once you recognize the minimax path structure, two standard algorithms apply: a modified Dijkstra using a min-heap where the priority of a state is the maximum elevation seen so far (not a sum), and a binary search on the answer combined with BFS or DFS to check feasibility. Both run efficiently on an n x n grid.

The Dijkstra-like approach uses a min-heap (priority queue) where each entry is (cost, row, col) and cost represents the maximum elevation encountered so far on the path to (row, col). The algorithm starts by pushing (grid[0][0], 0, 0) onto the heap and marking (0, 0) as visited. It then repeatedly pops the minimum-cost entry, and if that entry is (n-1, n-1), returns the cost as the answer.

For each popped cell (cost, r, c), the algorithm explores all four neighbors. For each unvisited neighbor (nr, nc), the new cost to reach it is max(cost, grid[nr][nc]): either the current running maximum or the neighbor's elevation, whichever is larger. This new cost is pushed onto the heap. The visited set ensures each cell is processed at most once, and because the heap always pops the minimum-cost entry next, the first time (n-1, n-1) is popped its cost is guaranteed to be optimal.

Time complexity is O(n^2 log n) because there are n^2 cells each inserted into the heap at most once, and each heap operation costs O(log(n^2)) = O(log n). Space complexity is O(n^2) for the heap and visited set. This is typically faster in practice than binary search plus BFS because it terminates as soon as the destination is reached rather than running full BFS passes for each candidate.

Standard Dijkstra works because the minimum-sum path obeys optimal substructure and the greedy choice of always expanding the cheapest known path is never regretted — a shorter prefix cannot be found later since all edge weights are non-negative. The same reasoning applies here when "cost" is the running maximum instead of a running sum.

Formally, when the heap pops (cost, r, c), it means no other path to (r, c) in the heap has a lower maximum elevation. This is because if there were a better path to (r, c) with a lower maximum, it would have been pushed with a smaller priority and would have been popped first. Once a cell is popped, its optimal cost is finalized — exactly like Dijkstra with non-negative weights.

The max operation satisfies the same monotonicity property as addition for Dijkstra: extending a path can only keep the cost the same or increase it (since max(x, y) >= x for any y >= 0). This monotonicity is the key property that allows greedy expansion by minimum current cost to always yield correct results for the entire path.

The binary search approach exploits the monotone structure of the problem: if a valid path exists at time t, it also exists at all times t' > t. This monotonicity means we can binary search on the answer in the range [0, n*n - 1]. For each candidate time mid, run a BFS or DFS from (0, 0) using only cells with elevation <= mid, and check whether (n-1, n-1) is reachable.

If the BFS succeeds (destination reachable), the answer is at most mid, so search the lower half. If BFS fails, the answer is greater than mid, so search the upper half. After O(log(n^2)) = O(log n) iterations of binary search, each costing O(n^2) for the BFS, total time is O(n^2 log n). This matches the Dijkstra approach asymptotically but has a larger constant due to running multiple full BFS passes.

The binary search approach is conceptually simpler and easier to verify by inspection: the BFS is completely standard, and the binary search predicate is a clean "can we reach destination using only cells with elevation <= t?" predicate. It is a good choice when clarity is prioritized. The Dijkstra approach is more elegant and typically faster because it terminates early once the destination is reached.

In Python, the Dijkstra min-heap solution uses heapq. Initialize heap = [(grid[0][0], 0, 0)] and visited = set(). In the main loop, heappop gives the minimum-cost entry. Push neighbors with heappush(heap, (max(cost, grid[nr][nc]), nr, nc)). The code is around 15 lines and handles all edge cases automatically. For the binary search version, use collections.deque for BFS; the predicate function is a 10-line BFS, and the binary search loop adds 8 more lines.

In Java, use PriorityQueue<int[]> with a comparator on the first element for the min-heap. Initialize with new int[]{grid[0][0], 0, 0}. Use a boolean[][] visited array. The four-direction exploration uses a standard int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}} array. Java's PriorityQueue.poll() returns the minimum-priority element. The solution is about 25 lines and runs efficiently within the n <= 50 constraints with room to spare.

A common mistake is using grid[nr][nc] alone as the heap priority instead of max(current_cost, grid[nr][nc]). If you only push the neighbor's raw elevation, you lose track of the running maximum along the path and will incorrectly compute the answer for paths that pass through high-elevation cells before descending. The heap entry must always represent the maximum elevation seen on the entire path from (0,0) to the current cell.

Trapping Rain Water II (LeetCode 407) uses the same min-heap pattern: start by pushing all boundary cells onto the heap with their elevations, then expand inward always taking the minimum-height frontier cell. The water trapped at each interior cell is determined by the maximum boundary height seen so far minus the cell's own elevation. Mastering Swim in Rising Water directly transfers to this harder 3D variant.

Shortest Path in Binary Matrix (LeetCode 1091) is the unweighted counterpart: standard BFS on a grid with 8-directional movement, finding the shortest path by hop count rather than minimax cost. Network Delay Time (LeetCode 743) is the canonical weighted-graph Dijkstra problem using sum of edge weights. Path With Minimum Effort (LeetCode 1631) is the closest relative — it also uses min-heap Dijkstra on a grid but minimizes the maximum absolute difference in heights between adjacent cells rather than the maximum absolute height.

The broader graph BFS and Dijkstra family includes problems like Cheapest Flights Within K Stops (LeetCode 787), Find the City With the Smallest Number of Neighbors (LeetCode 1334), and Minimum Cost to Reach Destination in Time (LeetCode 1928). Each adds a twist to the core shortest-path algorithm. Swim in Rising Water, with its minimax objective and grid structure, is an excellent bridge problem that deepens understanding of when and why the greedy heap expansion strategy remains valid under different cost functions.