Swim in Rising Water
Last Updated: April 5, 2026
Understanding the Problem
This problem is really about finding a path from the top-left corner to the bottom-right corner of a grid where the maximum elevation along the path is minimized. The "time" in the problem is a bit of a red herring. What matters is this: you can traverse a cell at time t only if its elevation is at most t. So the answer is simply the maximum elevation on the optimal path from (0,0) to (n-1, n-1).
Think of it this way: you want to find the path where the "tallest mountain" you have to cross is as short as possible. This is a classic minimax path problem. It's not about total cost (like shortest path), but about the worst single cell along the path.
Key Constraints:
1 <= n <= 50→ The grid has at most 2,500 cells. This is small enough for O(n^2 log n) or even O(n^4) approaches.0 <= grid[i][j] < n^2→ Values form a permutation of 0 to n^2-1. Every value is unique, so we can sort all cells by elevation and process them one at a time.Each value is unique→ No ties to worry about. This simplifies both binary search and union-find approaches.
Approach 1: Binary Search + BFS
Intuition
Here's a natural way to think about this: if someone told you "the answer is T," could you verify it? Absolutely. Just check if there's a path from (0,0) to (n-1,n-1) using only cells where grid[i][j] <= T. That's a standard BFS/DFS reachability check.
So the problem becomes: what's the smallest T where such a path exists? The answer is monotonic. If a path exists at time T, it also exists at time T+1 (water only rises). This monotonicity is the signal for binary search on the answer.
We binary search over possible values of T (from max(grid[0][0], grid[n-1][n-1]) to n*n - 1), and for each candidate, run a BFS to check if the path exists.
Algorithm
- Set
low = max(grid[0][0], grid[n-1][n-1])andhigh = n * n - 1. - While
low < high: - Compute
mid = (low + high) / 2. - Run BFS/DFS from
(0,0), only visiting cells wheregrid[i][j] <= mid. - If
(n-1, n-1)is reachable, sethigh = mid. - Otherwise, set
low = mid + 1. - Return
low.
Example Walkthrough
Code
- Time Complexity: O(n^2 log n). Binary search runs O(log(n^2)) = O(log n) iterations. Each iteration does a BFS over the entire grid in O(n^2).
- Space Complexity: O(n^2). The visited array and BFS queue each take O(n^2) space.
This approach works but runs a full BFS for every binary search iteration. What if we could find the answer in a single traversal by always expanding the cell with the smallest maximum elevation?
Approach 2: Modified Dijkstra's (Min-Heap)
Intuition
Instead of binary searching for the right threshold, we can solve this in one pass using a priority queue. The idea comes from Dijkstra's algorithm, but with a twist: instead of tracking the sum of edge weights, we track the maximum elevation along the path.
Start at (0,0). At each step, expand the unvisited neighbor with the smallest elevation. The "distance" to any cell is the maximum elevation encountered on the path to reach it. When we pop a cell from the min-heap, the maximum elevation along the best path to that cell is max(current_max, grid[r][c]).
The min-heap always processes the cell with the smallest required water level first. Once we reach (n-1, n-1), we know no other path could reach it with a smaller maximum elevation, because any unprocessed path goes through cells with higher elevations (those are still in the heap with larger keys).
The key invariant is that when we pop (maxElev, r, c), maxElev is the minimum possible maximum elevation to reach (r, c) from (0, 0). Adding more cells to the path can only increase or maintain the maximum.
Algorithm
- Push
(grid[0][0], 0, 0)onto a min-heap. Mark(0,0)as visited. - While the heap is not empty:
- Pop the cell
(maxElevation, r, c)with the smallest max elevation. - If
(r, c)is the destination(n-1, n-1), returnmaxElevation. - For each unvisited 4-directional neighbor
(nr, nc): - Compute
newMax = max(maxElevation, grid[nr][nc]). - Push
(newMax, nr, nc)onto the heap and mark it visited. - Return -1 (should never reach here for valid input).
Example Walkthrough
Code
- Time Complexity: O(n^2 log n). Each of the n^2 cells is pushed onto and popped from the heap at most once. Each heap operation is O(log(n^2)) = O(log n).
- Space Complexity: O(n^2). The visited array takes O(n^2) space, and the heap can hold up to O(n^2) elements.
The heap operations add a log factor to each cell processing. What if instead of searching for a path, we sorted all cells by elevation and added them one by one until start and end are connected?
Approach 3: Union-Find (Optimal)
Intuition
Imagine slowly raising the water level from 0 to n^2-1. At each level, one new cell becomes "available" (since all values are unique). The moment the cell at (0,0) and the cell at (n-1, n-1) become connected through available cells, you have your answer.
This is a classic Union-Find scenario. Sort all cells by elevation. Process them in order. For each cell, union it with any of its 4 neighbors that have already been processed. After each union, check if the start and end are in the same component. The first time they are, the current cell's elevation is the answer.
Algorithm
- Create a list of all cells
(elevation, row, col)and sort by elevation. - Initialize a Union-Find structure with n^2 elements.
- Create a boolean grid
availableinitialized to all false. - For each cell in sorted order:
- Mark
(r, c)as available. - Union
(r, c)with each adjacent cell that is already available. - If
find(0, 0) == find(n-1, n-1), return the current elevation. - Return the elevation of the last cell.
Example Walkthrough
Code
- Time Complexity: O(n^2 * alpha(n^2)) which is effectively O(n^2). We process n^2 cells, each with up to 4 union operations. With path compression and union by rank, each operation is nearly O(1).
- Space Complexity: O(n^2). The parent and rank arrays each take O(n^2) space, along with the position mapping and availability grid.