Back to DSA
Swim in Rising Water
hardAn n-by-n grid of distinct elevations is given. As time progresses, the water level rises uniformly: at time t, any cell with elevation at most t is submerged and swimmable. You may travel between 4-directionally adjacent cells only if both are submerged. Determine the earliest time at which you can travel from the top-left cell to the bottom-right cell.
Examples
Example 1:
Input:
grid = [[0,3],[2,1]]Output:
3Explanation: At time 3, cells with elevation 0, 2, 1, and 3 are all submerged, enabling a path.
Example 2:
Input:
grid = [[0,1,5],[2,3,4],[7,6,8]]Output:
6Explanation: At time 6, a path exists through elevations at most 6 from (0,0) to (2,2).
Hints
import java.util.*;
class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
boolean[][] visited = new boolean[n][n];
pq.offer(new int[]{0, 0, grid[0][0]});
visited[0][0] = true;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!pq.isEmpty()) {
int[] curr = pq.poll();
if (curr[0] == n - 1 && curr[1] == n - 1) return curr[2];
for (int[] d : dirs) {
int nr = curr[0] + d[0], nc = curr[1] + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
visited[nr][nc] = true;
pq.offer(new int[]{nr, nc, Math.max(curr[2], grid[nr][nc])});
}
}
}
return -1;
}
}Time complexity
O(n^2 log n)Space complexity
O(n^2)