Swim in Rising Water
MediumDijkstra where cost = the highest cell so far
Problem
Water rises over a grid of elevations; return the least time to travel from top-left to bottom-right.
Dijkstra-like: always step to the lowest reachable cell; the answer is the highest water level crossed.
The idea
Swim time is decided by the highest cell you must cross, so this is Dijkstra with a max-based cost. Relaxing a neighbour sets its cost to max(cost-so-far, its elevation). The priority queue always expands the cell reachable over the lowest peak, and the first time the bottom-right cell is settled you have the minimum time.
Step 1 of 13. Goal: the shortest distance from A to every other node. Start A = 0, everyone else = ∞ (unknown). dist [0, ∞, ∞, ∞, ∞], settled —.
1time[start] = height[start], all others = ∞2min-heap H = {(height[start], start)}3while H not empty:4 (t, cell) = pop-smallest from H5 for each neighbour nb of cell:6 step = max(t, height[nb])7 if step < time[nb]: time[nb] = step; push (step, nb)8return time[bottom-right]Input
- nodes
- 5, 6 edges
Memory
- dist
- [0, ∞, ∞, ∞, ∞]
- frontier
- —
Output
- settled
- —
- shortest dist
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- grid = [[0,2],[1,3]]
- Output:
- 3
- Explanation:
- You must wait until level 3 to cross.
Example 2
- Input:
- grid = [[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]]
- Output:
- 16
- Explanation:
- The best path peaks at height 16.
Example 3
- Input:
- grid = [[0]]
- Output:
- 0
- Explanation:
- Already at the exit → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.