Swim in Rising Water
You are given an n × n grid where grid[i][j]
Limits: 1 <= n <= 50, and the values of grid
The page gives two solutions.
Example 1
Output: 3
Explanation: the target cell has elevation 3, so nothing earlier than time 3 can work, and at time 3 every cell is under water.
Example 2
Output: 16
Explanation: the route along the top row, down the right side to 16, then left and around the outer ring never goes above 16.
Example 3
Output: 3
Explanation: you stand on (0, 0) from the start, so its own elevation 3 has to be under water first.
How to Think About It
Step 1: The cost of a path is its highest cell
Water only rises, so once a cell is under water it stays that way. A path from (0, 0) to the corner is usable at time t exactly when every cell on it has elevation at most t. The earliest time for one path is therefore the largest elevation on it, including both end cells.
Step 2: The answer is the best bottleneck
We want the path whose highest cell is as low as possible. A brute force tries t = 0, 1, 2 and so on and runs a flood fill each time. That is correct but costs up to n2 flood fills of n2 cells each.
Step 3: Dijkstra works with max instead of plus
Dijkstra's algorithm settles nodes in order of their best known cost. It only needs one property: extending a path never makes its cost smaller. With cost = highest elevation so far, stepping to a neighbour gives max(cost, grid[next])
So keep a min-heap of cells keyed by that cost. The first time a cell leaves the heap, no cheaper route to it exists, because every other route still in the heap already costs at least as much. When the corner leaves the heap, its cost is the answer. The same settling argument is explained in
Another angle: guess the time and check it
If you can cross at time t, you can also cross at any later time, since the same path stays under water. A yes or no question that flips once from no to yes can be answered with binary search. For one guess t, a BFS that only steps on cells with elevation at most t tells you whether the corner is reachable. This is
Walkthrough
Solution 1 on Example 2. Each row is one cell leaving the heap for the first time, with the cost it was settled at.
| Order | Cell settled | Elevation | Cost (time needed) |
|---|---|---|---|
| 1 to 5 | (0, 0) to (0, 4), the top row | 0, 1, 2, 3, 4 | 0, 1, 2, 3, 4 |
| 6 | (1, 4) | 5 | 5 |
| 7 | (2, 4) | 16 | 16 |
| 8 to 11 | (2, 3) to (2, 0), the middle row leftward | 15, 14, 13, 12 | 16 each |
| 12 to 13 | (3, 0), (4, 0) | 11, 10 | 16 each |
| 14 to 17 | (4, 1) to (4, 4), the bottom row rightward | 9, 8, 7, 6 | 16 each |
After cost 5, the cheapest cells next to the settled area are 16 on the right and 21 to 24 in row 1, so the heap picks 16. From there every cell is lower than 16, and the cost stays 16 until the corner (4, 4) is settled. The answer is 16.
Solution 1: Min-Heap on the Highest Elevation
swimInWater
- The starting cost: the heap starts with
, not 0. In Example 3 the start has elevation 3, and the answer is 3 even though the rest of the grid is lower.grid[0][0] - The new cost:
keeps the highest cell on the path. Adding elevations would answer a different question.Math.max(t, grid[nr][nc]) - Skipping repeats: a cell can be pushed by several neighbours. The
check drops every entry after the first one polled, which is the cheapest.done - Stopping early: the method returns when the corner is polled, not when it is pushed. A push only offers one route, while the poll proves no cheaper route is left. For n = 1 the start is the corner and the answer is
, which is 0.grid[0][0]
A common mistake is to push a neighbour with its own elevation, grid[nr][nc]
import java.util.PriorityQueue;
public class SwimInRisingWater {
public int swimInWater(int[][] grid) {
int n = grid.length;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
boolean[][] done = new boolean[n][n];
// {time needed to stand on this cell, row, col}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.add(new int[]{grid[0][0], 0, 0});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int t = top[0], r = top[1], c = top[2];
if (done[r][c]) continue; // a cheaper entry already settled this cell
done[r][c] = true;
if (r == n - 1 && c == n - 1) return t; // first poll of the corner is optimal
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !done[nr][nc]) {
// a path costs its highest cell
pq.add(new int[]{Math.max(t, grid[nr][nc]), nr, nc});
}
}
}
return -1; // not reached: every cell is connected to the corner
}
}
Solution 2: Binary Search on Time with BFS
This version binary searches for the smallest time t at which a BFS over cells with elevation at most t reaches the corner.
- The search range: the answer is at least the higher of the two end cells, since you must stand on both. It is at most n2 - 1, the highest value, when every cell is under water.
- Why binary search is allowed:
is false up to some time and true from then on. If it is true forcanReach(t) , the answer ismid or earlier, somid ; otherwisehi = mid .lo = mid + 1 - The BFS: it marks a cell as seen when it is added to the queue, so no cell is queued twice. It only enters a neighbour whose elevation is at most t.
- The start cell: the BFS never tests
. That is safe only becausegrid[0][0] already includes it.lo
On Example 2 the range starts at lo = 6hi = 24
| lo | hi | mid | canReach(mid) |
|---|---|---|---|
| 6 | 24 | 15 | false |
| 16 | 24 | 20 | true |
| 16 | 20 | 18 | true |
| 16 | 18 | 17 | true |
| 16 | 17 | 16 | true |
The range closes at 16, matching Solution 1. A common mistake is to start the search at lo = 0
import java.util.ArrayDeque;
import java.util.Deque;
public class SwimInRisingWaterBinarySearch {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int swimInWater(int[][] grid) {
int n = grid.length;
int lo = Math.max(grid[0][0], grid[n - 1][n - 1]); // both ends must be under water
int hi = n * n - 1; // every cell is under water by then
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canReach(grid, mid)) {
hi = mid; // mid works, so the answer is mid or earlier
} else {
lo = mid + 1; // mid is too early
}
}
return lo;
}
// BFS over cells whose elevation is at most t.
private boolean canReach(int[][] grid, int t) {
int n = grid.length;
boolean[][] seen = new boolean[n][n];
Deque<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{0, 0});
seen[0][0] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
if (cell[0] == n - 1 && cell[1] == n - 1) return true;
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) {
seen[nr][nc] = true;
queue.add(new int[]{nr, nc});
}
}
}
return false;
}
}
Complexity
- Solution 1 time: O(n2 log n). Each of the n2 cells is settled once and pushes at most 4 entries, so the heap sees O(n2) operations. Each costs log(n2) = 2 log n.
- Solution 1 space: O(n2). The
array has one flag per cell, and the heap can hold up to four entries per cell before the stale ones are polled.done - Solution 2 time: O(n2 log n). The search range has at most n2 values, so there are about log(n2) = 2 log n rounds. Each round runs one BFS that touches every cell at most once.
- Solution 2 space: O(n2). Each BFS allocates a fresh
grid of n2 flags, and its queue can hold a large share of the cells at once.seen
Which One to Use
Both solutions run in O(n2 log n) and return the same answers, and for n <= 50 either one is instant. Solution 1 is one pass and often stops early, as soon as the corner is settled. Solution 2 repeats a plain BFS about a dozen times, but each piece is simple and easy to test on its own. Choose Solution 1 when you recognise a "minimise the worst step" path problem. Choose Solution 2 when checking a single guess is easy and the answers are monotonic, as in
Spreading through a height grid from the edges, without a clock, is