Skip to content
AI360Xpert
Back to Advanced Graphs
Hard

Swim in Rising Water

You are given an `n x n` integer matrix `grid` where each value `grid[i][j]` represents the elevation at that point `(i, j)`. The rain starts to fall. At time `t`, the depth of the water everywhere is `t`. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most `t`. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim. Return the least time until you can reach the bottom right square `(n - 1, n - 1)` if you start at the top left square `(0, 0)`.

Examples

Input:grid = [[0,2],[1,3]]
Output:3
At time 0, you are in grid location (0, 0). You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0. You cannot reach point (1, 1) until time 3. When the depth of water is 3, we can swim anywhere inside the grid.
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
The final route is (0,0) -> (0,4) -> (1,4) -> (2,4) -> (2,0) -> (4,0) -> (4,4). The maximum elevation in this route is 16.

Constraints

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 50
  • 0 <= grid[i][j] < n^2
  • Each value grid[i][j] is unique.

Dijkstra's Algorithm

Approach

We need to find a path from the start to the end where the maximum elevation encountered is minimized. This can be solved using Dijkstra's algorithm with a min-heap. The heap stores `(max_elevation_so_far, row, col)`. At each step, we extract the cell with the minimum `max_elevation_so_far`. If we reach the destination `(n-1, n-1)`, this value is our answer. Otherwise, we explore its 4 neighbors, calculate the new maximum elevation `max(max_elevation_so_far, grid[neighbor_row][neighbor_col])`, and push it to the heap if the neighbor hasn't been visited.

Complexity Analysis

Time Complexity
O(N^2 log N)
Space Complexity
O(N^2)

The grid has N^2 cells. In the worst case, all cells are pushed to the min-heap. Heap operations take O(log(N^2)) = O(log N) time. The space complexity is O(N^2) for the heap and visited set.

Solution.java
class Solution {    public int swimInWater(int[][] grid) {        int n = grid.length;        // Min-heap stores {max_elevation, row, col}        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);        boolean[][] visited = new boolean[n][n];                minHeap.offer(new int[]{grid[0][0], 0, 0});        visited[0][0] = true;                int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};                while (!minHeap.isEmpty()) {            int[] curr = minHeap.poll();            int t = curr[0];            int r = curr[1];            int c = curr[2];                        // Reached destination            if (r == n - 1 && c == n - 1) {                return t;            }                        for (int[] dir : dirs) {                int nr = r + dir[0];                int nc = c + dir[1];                                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {                    visited[nr][nc] = true;                    // The time required to reach neighbor is the max of the path so far and the neighbor's elevation                    minHeap.offer(new int[]{Math.max(t, grid[nr][nc]), nr, nc});                }            }        }                return 0;    }}