DSA problem
Swim in Rising Water
You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j). The rain starts to fall. At time t, the water level is t everywhere; you can swim from a cell to a 4-directionally adjacent cell only if both cells have elevation at most t. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (n-1, n-1). Return the least time until you can reach the bottom-right cell.
This is another bottleneck shortest-path problem. The "cost" of a path is the maximum elevation across all visited cells, and we want the path whose maximum is as small as possible. Once t reaches that minimum maximum elevation, water has filled deep enough for the path to be swimmable.
A naive solution would binary-search the answer: pick a candidate t, do a BFS over cells with elevation <= t from the top-left, and check whether the bottom-right is reachable. That works in O(n^2 log(maxVal)) time and is a perfectly valid approach.
The cleaner approach uses Dijkstra-like exploration with a min-heap keyed by current maximum elevation. Start with (grid[0][0], 0, 0). Pop the cell with the smallest current max, and for each unvisited 4-directional neighbor push max(current_max, grid[nr][nc]). The first time (n-1, n-1) is popped, its max equals the answer. Running time is O(n^2 log n) and space is O(n^2). This problem is also in the Union-Find category, but slug-suffix -sp makes the Shortest-Path version unique.
Examples
grid = [[0,2],[1,3]]3grid = [[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]]16grid = [[0,1],[2,3]]3Constraints
- n == grid.length
- n == grid[i].length
- 1 <= n <= 50
- 0 <= grid[i][j] < n^2
- Each value grid[i][j] is unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.