Swim in Rising Water

HARD

Description

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:

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:

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] < n²
Each value grid[i][j] is unique.

Approaches

Checkout 3 different approaches to solve Swim in Rising Water. Click on different approaches to view the approach and algorithm in detail.

Dijkstra's Algorithm / Best-First Search

This problem can be viewed as finding a path from the top-left to the bottom-right corner that minimizes the highest "cost" (elevation) of any cell along the path. This is a classic application for Dijkstra's algorithm or a Best-First Search. We use a priority queue to always explore the path that has the minimum-highest-elevation-so-far. The algorithm greedily expands paths with lower water level requirements, guaranteeing that when we first reach the destination, it will be via a path that requires the least possible time.

Algorithm

Model the grid as a graph where each cell is a node.
The problem is to find a path from (0,0) to (n-1,n-1) that minimizes the maximum elevation on the path. This is a bottleneck shortest path problem.
Use a priority queue (min-heap) to implement a Best-First Search, which is a variant of Dijkstra's algorithm. The priority queue will store (time, row, col) and will be ordered by time.
Initialize a visited array to keep track of visited cells.
Start by pushing the initial state (grid[0][0], 0, 0) into the priority queue.
While the priority queue is not empty: a. Pop the cell (t, r, c) with the minimum time t. b. If (r, c) is the destination, t is the minimum time required. Return t. c. For each unvisited neighbor (nr, nc) of (r, c): i. Mark the neighbor as visited. ii. The time to reach this neighbor is the maximum of the current time t and the neighbor's elevation grid[nr][nc]. iii. Push (max(t, grid[nr][nc]), nr, nc) into the priority queue.

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        // Min-heap storing {max_elevation_so_far, row, col}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[][] visited = new boolean[n][n];
        
        pq.offer(new int[]{grid[0][0], 0, 0});
        visited[0][0] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!pq.isEmpty()) {
            int[] cell = pq.poll();
            int t = cell[0];
            int r = cell[1];
            int c = cell[2];

            if (r == n - 1 && c == n - 1) {
                return t;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    int newTime = Math.max(t, grid[nr][nc]);
                    pq.offer(new int[]{newTime, nr, nc});
                }
            }
        }
        return -1; // Should not be reached given the problem constraints
    }
}

Complexity Analysis

Time Complexity: O(n^2 * log(n^2)) which simplifies to O(n^2 * log(n)). Each of the `n^2` cells is added to and removed from the priority queue at most once. Each operation on the priority queue takes O(log(n^2)) time.Space Complexity: O(n^2) - For the `visited` array and the priority queue, which can store up to O(n^2) elements.

Pros and Cons

Pros:

It's a direct and elegant solution for this type of bottleneck shortest path problem.
Generally more efficient than the binary search approach as it explores the grid in a more targeted way.

Cons:

Slightly more complex to understand and implement than a simple BFS if one is not familiar with Dijkstra's algorithm or priority queues.

Code Solutions

Checking out 3 solutions in different languages for Swim in Rising Water. Click on different languages to view the code.

class Solution {
private
  int[] p;
public
  int swimInWater(int[][] grid) {
    int n = grid.length;
    p = new int[n * n];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    int[] hi = new int[n * n];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        hi[grid[i][j]] = i * n + j;
      }
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int t = 0; t < n * n; ++t) {
      int i = hi[t] / n;
      int j = hi[t] % n;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k];
        int y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] <= t) {
          p[find(x * n + y)] = find(i * n + j);
        }
        if (find(0) == find(n * n - 1)) {
          return t;
        }
      }
    }
    return -1;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

Video Solution

Watch the video walkthrough for Swim in Rising Water

Algorithms:

Binary SearchDepth-First SearchBreadth-First SearchUnion Find

Data Structures:

ArrayHeap (Priority Queue)Matrix

Companies:

DoorDash |DE Shaw |PhonePe |WeRide |