Swim in Rising Water (LeetCode 778)
You get an n x n elevation map grid, where grid[i][j] is the height of cell (i, j). Rain raises the water level uniformly over time; at time t the whole grid is flooded to depth t.
At any moment you can swim, instantly and any distance, between two 4-directionally adjacent cells as long as both cells' elevations are already at or below the current water level t.
Return the earliest time t at which a swimmable route connects the top-left cell (0, 0) to the bottom-right cell (n - 1, n - 1).
Worked 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]]16⚖️Formal Constraints & Bounds
n == grid.lengthn == grid[i].length1 <= n <= 500 <= grid[i][j] < n^2Each value
grid[i][j]is unique
Core Insight
Swim in Rising Water is Path With Minimum Effort's node-weighted twin: the bottleneck value being tracked is grid[r][c] itself (the cost of ENTERING a cell) rather than a height difference between two cells (the cost of an EDGE), but the min-heap + max-relaxation + visited-on-pop machinery is identical.
Real-World Scenario & Production Applications
Flood-response and network-provisioning problems where a resource (a road, a server, a channel) only becomes usable once a global threshold crosses its own individual requirement — the moment you can "afford" every cell in the cheapest valid route is dictated by the single most expensive cell that route is forced to touch.
Subproblems & Recurrence Decomposition3 Phases
Unlike edge-weighted Dijkstra variants, the cost here lives ON each cell (its elevation). Seed the heap with the start cell's own elevation and mark it visited immediately (visited-on-push is safe here since elevations are unique).
min_heap = [(grid[0][0], 0, 0)]
visited = [[False] * n for _ in range(n)]
visited[0][0] = TrueStep-by-Step Execution Trace Table
Step-by-Step Minimax Relaxation Trace (grid = [[0,2],[1,3]])
| Step | Popped Cell (r, c) | Elevation | ans = max(ans, elevation) | Destination? | Neighbors Pushed |
|---|---|---|---|---|---|
| 1 | (0, 0) | 0 | ans = 0 | No | Push (0,1) elev=2, (1,0) elev=1 |
| 2 | (1, 0) | 1 | ans = 1 | No | Push (1,1) elev=3 |
| 3 | (0, 1) | 2 | ans = 2 | No | (1,1) already queued |
| 4 | (1, 1) | 3 | ans = 3 | Yes -- return 3 | -- |
grid = [[0,2],[1,3]]3Step-by-Step Minimax Relaxation Trace (grid = [[0,2],[1,3]])
| Step | Popped Cell (r, c) | Elevation | ans = max(ans, elevation) | Destination? | Neighbors Pushed |
|---|---|---|---|---|---|
| 1 | (0, 0) | 0 | ans = 0 | No | Push (0,1) elev=2, (1,0) elev=1 |
| 2 | (1, 0) | 1 | ans = 1 | No | Push (1,1) elev=3 |
| 3 | (0, 1) | 2 | ans = 2 | No | (1,1) already queued |
| 4 | (1, 1) | 3 | ans = 3 | Yes -- return 3 | -- |
| 1 | n = len(grid) |
| 2 | visited = [[False] * n for _ in range(n)] |
| 3 | min_heap = [(grid[0][0], 0, 0)] |
| 4 | visited[0][0] = True |
| 5 | ans = 0 |
| 6 | while min_heap: |
| 7 | elevation, r, c = heappop(min_heap) |
| 8 | ans = max(ans, elevation) |
| 9 | if (r, c) == (n - 1, n - 1): |
| 10 | return ans |
| 11 | for each neighbor (nr, nc) in the 4 directions: |
| 12 | if (nr, nc) is inside the grid and not visited[nr][nc]: |
| 13 | visited[nr][nc] = True |
| 14 | heappush(min_heap, (grid[nr][nc], nr, nc)) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
To swim from top-left to bottom-right, the water elevation must be at least the maximum elevation along the chosen path. This is a minimax bottleneck path problem on a grid. Using a min-heap initialized at (grid[0][0], 0, 0), we greedily expand into adjacent cells, updating the required water level to . The first time the destination cell is popped from the heap, the minimal required time is achieved.
🏊 The Analogy: Waiting Out the Flood
Imagine a courtyard of stepping-stones at different heights, and water that rises minute by minute. You may step onto any adjacent stone the instant the water level has risen enough to cover it (or it was already exposed) — you're never blocked by a stone being "too high," only ever by the water not yet being deep enough for the path you'd have to take. To cross with the least possible total waiting time, you should always advance next onto whichever reachable stone has the LOWEST elevation you haven't already claimed — because that's the stone that becomes safe to stand on soonest. The total time you must wait is dictated by the single tallest stone your best route was ever forced to step on, exactly like the "worst step" in Path With Minimum Effort.
🔑 The Key Idea in the Code
Popping cells from a min-heap in increasing order of elevation guarantees every cell is finalized with its true minimum "time to become reachable." The moment the destination cell is popped, ans already holds the smallest possible bottleneck across every reachable route — no further exploration can ever lower it, so it's safe to return immediately, the same early-exit guarantee classic Dijkstra gives you.
Starting elevation bottleneck neglect: Forgetting that the time at start is at least
grid[0][0]. Initializing the starting heap entry with time0instead ofgrid[0][0]produces incorrect results whengrid[0][0] > 0.Edge relaxation time calculation: Setting neighbor water level to
time + grid[nr][nc]instead ofmax(time, grid[nr][nc]). Water rises globally; the time needed to cross into a neighbor is the maximum of the current time and the neighbor's platform height.Not marking visited on push: In this min-heap Dijkstra variant on a grid, waiting until pop to mark cells visited allows the same grid cell to be added to the heap multiple times, blowing up heap size to .
Summing instead of maxing in a minimax relaxation (Path With Minimum Effort, Swim in Rising Water).
new_effort = effort + step_costanswers a completely different question thannew_effort = max(effort, step_cost). The moment a problem defines cost as "the worst single step," the relaxation operator must change from+tomax, or the algorithm silently computes the wrong quantity while still looking like valid Dijkstra code.Confusing node-weighted and edge-weighted bottlenecks (Path With Minimum Effort vs. Swim in Rising Water). Path With Minimum Effort's cost lives on the EDGE between two cells (
abs(heights[nr][nc] - heights[r][c])); Swim in Rising Water's cost lives ON the cell itself (grid[r][c]). Using an edge-difference formula for Swim in Rising Water, or vice versa, produces a plausible-looking but wrong answer.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Path 'cost' is the maximum value of something ON each visited cell (node-weighted), not on each edge, combined with a 4-directional grid.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: popping cells from a min-heap in increasing elevation order means every popped cell's ans = max(ans, elevation) already holds its true minimum required wait time; nothing explored later can lower it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Marking a cell visited on push instead of before pushing (or forgetting to mark visited at all), which lets the same cell be pushed many times and makes the heap much larger than the number of cells.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I run a Dijkstra variant where the priority is a cell's own elevation rather than an edge weight. I pop the lowest-elevation reachable cell, track ans = max(ans, elevation), and return ans the instant I pop the destination. This is the exact same minimax-relaxation idea as Path With Minimum Effort, just with the bottleneck value living on nodes instead of edges. It's also solvable via binary search on the answer plus BFS/Union-Find to test reachability at each candidate time. Runs in O(N^2 log N) time for an N x N grid."
Complexity & Mathematical Proof
O(N^2 log N)
Look at the execution steps: each of the N^2 cells is pushed onto the min-heap exactly once (marked visited before pushing), and each heap push/pop over a heap of size O(N^2) costs O(log(N^2)) = O(log N).
O(N^2) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. The visited table is O(N^2), and the min-heap holds at most O(N^2) entries.
T(N) = O(N^2 log N)
Derivation Progression
O(log(N^2)) = O(log N)
Each pop removes the lowest-elevation reachable cell from a heap of size up to O(N^2).
4 · O(log N) per cell
Each cell is marked visited and pushed exactly once across all its neighbors, avoiding duplicate heap entries.
N^2 · O(log N) = O(N^2 log N)
Every one of the N^2 cells contributes one O(log N) heap operation.
Variable Definitions
Side length of the N x N grid
Memory Architecture & Bounds
O(1) Iterative
O(N^2) visited table and min-heap entries
O(1) Minimum time integer
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "least time until you can reach bottom right", "swim in rising water". Node-weighted bottleneck path: water level must reach at least the elevation of each visited cell. Modified Dijkstra via Min-Heap.
. Time budget: runs in ms.
Swim in Rising Water (LeetCode 778)
You get an n x n elevation map grid, where grid[i][j] is the height of cell (i, j). Rain raises the water level uniformly over time; at time t the whole grid is flooded to depth t.
At any moment you can swim, instantly and any distance, between two 4-directionally adjacent cells as long as both cells' elevations are already at or below the current water level t.
Return the earliest time t at which a swimmable route connects the top-left cell (0, 0) to the bottom-right cell (n - 1, n - 1).
Worked 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]]16⚖️Formal Constraints & Bounds
n == grid.lengthn == grid[i].length1 <= n <= 500 <= grid[i][j] < n^2Each value
grid[i][j]is unique
Core Insight
Swim in Rising Water is Path With Minimum Effort's node-weighted twin: the bottleneck value being tracked is grid[r][c] itself (the cost of ENTERING a cell) rather than a height difference between two cells (the cost of an EDGE), but the min-heap + max-relaxation + visited-on-pop machinery is identical.
Real-World Scenario & Production Applications
Flood-response and network-provisioning problems where a resource (a road, a server, a channel) only becomes usable once a global threshold crosses its own individual requirement — the moment you can "afford" every cell in the cheapest valid route is dictated by the single most expensive cell that route is forced to touch.
Subproblems & Recurrence Decomposition3 Phases
Unlike edge-weighted Dijkstra variants, the cost here lives ON each cell (its elevation). Seed the heap with the start cell's own elevation and mark it visited immediately (visited-on-push is safe here since elevations are unique).
min_heap = [(grid[0][0], 0, 0)]
visited = [[False] * n for _ in range(n)]
visited[0][0] = TrueStep-by-Step Execution Trace Table
Step-by-Step Minimax Relaxation Trace (grid = [[0,2],[1,3]])
| Step | Popped Cell (r, c) | Elevation | ans = max(ans, elevation) | Destination? | Neighbors Pushed |
|---|---|---|---|---|---|
| 1 | (0, 0) | 0 | ans = 0 | No | Push (0,1) elev=2, (1,0) elev=1 |
| 2 | (1, 0) | 1 | ans = 1 | No | Push (1,1) elev=3 |
| 3 | (0, 1) | 2 | ans = 2 | No | (1,1) already queued |
| 4 | (1, 1) | 3 | ans = 3 | Yes -- return 3 | -- |
grid = [[0,2],[1,3]]3Step-by-Step Minimax Relaxation Trace (grid = [[0,2],[1,3]])
| Step | Popped Cell (r, c) | Elevation | ans = max(ans, elevation) | Destination? | Neighbors Pushed |
|---|---|---|---|---|---|
| 1 | (0, 0) | 0 | ans = 0 | No | Push (0,1) elev=2, (1,0) elev=1 |
| 2 | (1, 0) | 1 | ans = 1 | No | Push (1,1) elev=3 |
| 3 | (0, 1) | 2 | ans = 2 | No | (1,1) already queued |
| 4 | (1, 1) | 3 | ans = 3 | Yes -- return 3 | -- |
| 1 | n = len(grid) |
| 2 | visited = [[False] * n for _ in range(n)] |
| 3 | min_heap = [(grid[0][0], 0, 0)] |
| 4 | visited[0][0] = True |
| 5 | ans = 0 |
| 6 | while min_heap: |
| 7 | elevation, r, c = heappop(min_heap) |
| 8 | ans = max(ans, elevation) |
| 9 | if (r, c) == (n - 1, n - 1): |
| 10 | return ans |
| 11 | for each neighbor (nr, nc) in the 4 directions: |
| 12 | if (nr, nc) is inside the grid and not visited[nr][nc]: |
| 13 | visited[nr][nc] = True |
| 14 | heappush(min_heap, (grid[nr][nc], nr, nc)) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
To swim from top-left to bottom-right, the water elevation must be at least the maximum elevation along the chosen path. This is a minimax bottleneck path problem on a grid. Using a min-heap initialized at (grid[0][0], 0, 0), we greedily expand into adjacent cells, updating the required water level to . The first time the destination cell is popped from the heap, the minimal required time is achieved.
🏊 The Analogy: Waiting Out the Flood
Imagine a courtyard of stepping-stones at different heights, and water that rises minute by minute. You may step onto any adjacent stone the instant the water level has risen enough to cover it (or it was already exposed) — you're never blocked by a stone being "too high," only ever by the water not yet being deep enough for the path you'd have to take. To cross with the least possible total waiting time, you should always advance next onto whichever reachable stone has the LOWEST elevation you haven't already claimed — because that's the stone that becomes safe to stand on soonest. The total time you must wait is dictated by the single tallest stone your best route was ever forced to step on, exactly like the "worst step" in Path With Minimum Effort.
🔑 The Key Idea in the Code
Popping cells from a min-heap in increasing order of elevation guarantees every cell is finalized with its true minimum "time to become reachable." The moment the destination cell is popped, ans already holds the smallest possible bottleneck across every reachable route — no further exploration can ever lower it, so it's safe to return immediately, the same early-exit guarantee classic Dijkstra gives you.
Starting elevation bottleneck neglect: Forgetting that the time at start is at least
grid[0][0]. Initializing the starting heap entry with time0instead ofgrid[0][0]produces incorrect results whengrid[0][0] > 0.Edge relaxation time calculation: Setting neighbor water level to
time + grid[nr][nc]instead ofmax(time, grid[nr][nc]). Water rises globally; the time needed to cross into a neighbor is the maximum of the current time and the neighbor's platform height.Not marking visited on push: In this min-heap Dijkstra variant on a grid, waiting until pop to mark cells visited allows the same grid cell to be added to the heap multiple times, blowing up heap size to .
Summing instead of maxing in a minimax relaxation (Path With Minimum Effort, Swim in Rising Water).
new_effort = effort + step_costanswers a completely different question thannew_effort = max(effort, step_cost). The moment a problem defines cost as "the worst single step," the relaxation operator must change from+tomax, or the algorithm silently computes the wrong quantity while still looking like valid Dijkstra code.Confusing node-weighted and edge-weighted bottlenecks (Path With Minimum Effort vs. Swim in Rising Water). Path With Minimum Effort's cost lives on the EDGE between two cells (
abs(heights[nr][nc] - heights[r][c])); Swim in Rising Water's cost lives ON the cell itself (grid[r][c]). Using an edge-difference formula for Swim in Rising Water, or vice versa, produces a plausible-looking but wrong answer.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Path 'cost' is the maximum value of something ON each visited cell (node-weighted), not on each edge, combined with a 4-directional grid.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: popping cells from a min-heap in increasing elevation order means every popped cell's ans = max(ans, elevation) already holds its true minimum required wait time; nothing explored later can lower it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Marking a cell visited on push instead of before pushing (or forgetting to mark visited at all), which lets the same cell be pushed many times and makes the heap much larger than the number of cells.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I run a Dijkstra variant where the priority is a cell's own elevation rather than an edge weight. I pop the lowest-elevation reachable cell, track ans = max(ans, elevation), and return ans the instant I pop the destination. This is the exact same minimax-relaxation idea as Path With Minimum Effort, just with the bottleneck value living on nodes instead of edges. It's also solvable via binary search on the answer plus BFS/Union-Find to test reachability at each candidate time. Runs in O(N^2 log N) time for an N x N grid."
Complexity & Mathematical Proof
O(N^2 log N)
Look at the execution steps: each of the N^2 cells is pushed onto the min-heap exactly once (marked visited before pushing), and each heap push/pop over a heap of size O(N^2) costs O(log(N^2)) = O(log N).
O(N^2) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. The visited table is O(N^2), and the min-heap holds at most O(N^2) entries.
T(N) = O(N^2 log N)
Derivation Progression
O(log(N^2)) = O(log N)
Each pop removes the lowest-elevation reachable cell from a heap of size up to O(N^2).
4 · O(log N) per cell
Each cell is marked visited and pushed exactly once across all its neighbors, avoiding duplicate heap entries.
N^2 · O(log N) = O(N^2 log N)
Every one of the N^2 cells contributes one O(log N) heap operation.
Variable Definitions
Side length of the N x N grid
Memory Architecture & Bounds
O(1) Iterative
O(N^2) visited table and min-heap entries
O(1) Minimum time integer
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "least time until you can reach bottom right", "swim in rising water". Node-weighted bottleneck path: water level must reach at least the elevation of each visited cell. Modified Dijkstra via Min-Heap.
. Time budget: runs in ms.