Swim in Rising Water
You're given an n x n grid where grid[r][c] is the elevation of that cell, and every value from 0 to n^2 - 1 appears exactly once. Rain falls and the water level rises: at time t, the water depth is t everywhere. You can swim from a cell to a neighbor up, down, left, or right when both elevations are at most t, and swimming itself takes no time. Return the least time t at which you can get from the top-left cell to the bottom-right cell.
Examples
grid = [[0,3],[2,1]] returns 2
Going down through the 2 and then right to the 1 never touches anything higher than 2. Going right first would cross the 3.
grid = [[0,1,2],[7,8,3],[6,5,4]] returns 4
Follow the top row and then the right column, 0, 1, 2, 3, 4. The highest cell on that route is the destination itself.
grid = [[3,0],[1,2]] returns 3
The starting cell has elevation 3, so nothing can happen before time 3.
Constraints
- 1 <= n <= 50
- 0 <= grid[i][j] < n^2
- Every value in grid is unique.
Hints
For a fixed route, how long do you have to wait before you can swim all of it?
You want the path whose highest cell is as low as possible. Dijkstra's algorithm still works when a path's cost is its maximum instead of its sum.
Push (grid[0][0], 0, 0) on a min-heap. Pop the lowest level, mark the cell visited, and push each unvisited neighbor with max(level, grid[nr][nc]). Return the level when you pop the bottom-right cell.
Drill This: Your Approach First
Approach
The time a route needs is the highest elevation on it, so the task is to minimize the maximum cell on a path. Dijkstra's algorithm handles that with max in place of addition: start a min-heap with (grid[0][0], 0, 0), repeatedly pop the cell with the lowest level so far, and push each unvisited neighbor with max(level, its elevation). The first time the bottom-right cell is popped, its level is the answer. O(n^2 log n) time and O(n^2) space. Binary searching t with a flood fill at each step, or adding cells in order of elevation to a union-find, also works.
Time
O(n^2 log n)
Space
O(n^2)
Pitfall
Solutions
class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
boolean[][] visited = new boolean[n][n];
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
heap.offer(new int[] {grid[0][0], 0, 0});
while (!heap.isEmpty()) {
int[] top = heap.poll();
int level = top[0], r = top[1], c = top[2];
if (visited[r][c]) continue;
visited[r][c] = true;
if (r == n - 1 && c == n - 1) return level;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
heap.offer(new int[] {Math.max(level, grid[nr][nc]), nr, nc});
}
}
}
return -1;
}
}import heapq
class Solution:
def swimInWater(self, grid) -> int:
n = len(grid)
visited = [[False] * n for _ in range(n)]
heap = [(grid[0][0], 0, 0)]
while heap:
level, r, c = heapq.heappop(heap)
if visited[r][c]:
continue
visited[r][c] = True
if r == n - 1 and c == n - 1:
return level
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
heapq.heappush(heap, (max(level, grid[nr][nc]), nr, nc))
return -1