Skip to content

778. 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).

Example 1:

img

Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
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.

Example 2:

img

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
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Constraints:

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

Solution:

class Solution {
    public int swimInWater(int[][] grid) {
        // Intialize the priority queue to store cells in ascedning order of water level
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[2]-b[2]));
        // Direction array fro moving right, left, down, up
        int[][] directions = {{0, 1}, {0, -1}, {1,0}, {-1,0}};
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        // Visited array to keep track of processed cells

        for (boolean[] row : visited){
            Arrays.fill(row, false);
        }

        // Add the startting cell (0, 0) with its water level to the priority queue
        pq.add(new int[]{0, 0, grid[0][0]});

        // Process the priority queue until it's empty
        while(!pq.isEmpty()){
            // Retrieve and remove the call with the smallest water level
            int[] cur = pq.poll();
            // Skip if the cell has already been visited
            if (visited[cur[0]][cur[1]]){
                continue;
            }


            // If the cell is the bottom-right corner, return its water leve
            if (cur[0] == n-1 && cur[1] == n - 1){
                return cur[2]; // the target
            }


            // Mark the cell as visited
            visited[cur[0]][cur[1]] = true;


            // Check the four possible moves (right, left, down, up)
            for (int[] direction : directions){
                int x = cur[0] + direction[0];
                int y = cur[1] + direction[1];

                // If the move is within bounds and the cell hasn't been visited
                if (x >= 0 && y >= 0 && x < n && y < n && !visited[x][y]){
                    // Add the new cell to the priority queue with the updated water level
                    pq.offer(new int[]{x,y, Math.max(cur[2], grid[x][y])});
                }
            }

        }

        // If the loop completes without finding the bottom-right corner, return 0
        return 0;

    }
}

// TC: O(n^2logn)
// SC: O(n^2)