Swim in Rising Water
Hard Dijkstra (minimax) on a grid
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
At time t the water level is t, and you can swim between adjacent cells whose heights are both at most t. Return the least time to get from the top-left to the bottom-right.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the earliest time you can swim from the top-left to the bottom-right.
Why this works: the time for a path is its highest cell; minimise that with a min-heap Dijkstra.
Example: [[0,2],[1,3]]
best path 0 → 1 → 3 → time 3✦Hints open one at a time
↗Approach
Min-heap of (maxHeightSoFar, r, c) starting with grid[0][0]. Pop the smallest; when it's the target, return. Push unvisited neighbours with max(current, their height).
</>Solution (Java)
import java.util.*;
class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
boolean[][] seen = new boolean[n][n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // {time, r, c}
pq.offer(new int[]{grid[0][0], 0, 0});
seen[0][0] = true;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (true) {
int[] cur = pq.poll();
if (cur[1] == n - 1 && cur[2] == n - 1) return cur[0];
for (int[] d : dirs) {
int r = cur[1] + d[0], c = cur[2] + d[1];
if (r < 0 || c < 0 || r >= n || c >= n || seen[r][c]) continue;
seen[r][c] = true;
pq.offer(new int[]{Math.max(cur[0], grid[r][c]), r, c}); // the path's highest cell
}
}
}
}!Common mistake
Using plain BFS by steps — the number of moves doesn't matter, only the highest cell on the path.
- Time: O(n² log n).
- Space: O(n²).