Solution: Swim in Rising Water

Statement

Given an $n \times n$ grid (2D matrix) where each cell grid[i][j] represents the elevation at position (i, j).

Once it starts to rain, the water level rises over time. At any given time t, the water depth across the grid equals t. A swimmer can move from one cell to an adjacent cell (up, down, left, or right) if both cells have elevations less than or equal to the current water level t.

If the elevation condition is satisfied, a swimmer can swim any distance instantly. However, he cannot move outside the grid boundaries.

Return the minimum time t at which it becomes possible to swim from the top-left cell $(0, 0)$ to the bottom-right cell $(n - 1, n - 1)$.

Constraints:

• $n ==$ grid.length

• $n ==$ grid[i].length

• $1 \leq$ $n$ $\leq 50$

• $0 \leq$ grid[i][j] $< n^2$

• Each value grid[i][j] is unique.

Solution

This solution employs a greedy, Dijkstra-like algorithm to simulate the gradual rise of water and determine the earliest possible time when a valid path exists from the start to the finish. To do this, the algorithm uses a min heap to always explore the cell with the lowest elevation next. This ensures that we always move toward the most accessible path, minimizing the highest elevation (i.e., water level) encountered along the way.

At each step:

• The cell with the current lowest elevation is popped from the heap.

• If the elevation of the popped cell exceeds the previously recorded maximum elevation, the maximum elevation is updated. This value represents the highest elevation encountered along the path, corresponding to the minimum water level required to reach this point.

• If the destination cell (n - 1, n - 1) is reached, max elevation is returned immediately, as it indicates the minimum time at which the swimmer can reach the goal.

The algorithm then explores all valid, unvisited neighbors (up, down, left, right) of the popped cell. Each neighbor is:

• Added to the heap with its elevation and coordinates.

• Marked as visited to avoid cycles or redundant work.

This process repeats until the destination cell (n - 1, n - 1) is reached. The maximum elevation encountered along the path corresponds to the minimum time required for the swimmer to complete the journey.

The steps of the algorithm are as follows:

1. Initialize n as the grid size, visited with starting cell coordinates (0, 0), and minHeap with the starting cell (grid[0][0], 0, 0).

2. Set maxElevation to 0 to track the highest elevation on the path.

3. While the heap is not empty:

   1. Pop the cell with the lowest elevation from the heap: (elevation, row, col).

   2. Update maxElevation as the maximum between the current maxElevation and the elevation of this cell.

   3. If the current cell is the bottom-right corner (n-1, n-1), return maxElevation as the minimum time required to swim to the end.

4. Explore neighboring cells (up, down, left, right): For each direction:

   1. Compute newRow and newCol. From the current cell (row, col), compute adjacent positions using up: (row - 1, col), down: (row + 1, col), left: (row, col - 1), right: (row, col + 1).

   2. If the new position is inside the grid, i.e, 0 <= newRow < n and 0 <= newCol < n, and has not been visited yet (not in the visited set):

      1. Add the new cell to the heap: (grid[newRow][newCol], newRow, newCol).

      2. Mark the new cell as visited by adding (newRow, newCol) to the visited set.

Let’s look at the following illustration to get a better understanding of the solution: