Statementâ–¼
Given an 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
Constraints:
n== grid.length
n== grid[i].length
1≤ n ≤50 0≤ grid[i][j]
<Â n2 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:
Initialize
n
as the grid size,visited
with starting cell coordinates (0, 0), andmin_heap
with the starting cell(grid[0][0], 0, 0)
.Set
max_elevation
to 0 to track the highest elevation on the path.While the heap is not empty:
Pop the cell with the lowest elevation from the heap:
(elevation, row, col)
.Update
max_elevation
as the maximum between the currentmax_elevation
and the elevation of this cell.If the current cell is the bottom-right corner
(n-1, n-1)
, returnmax_elevation
as the minimum time required to swim to the end.
Explore neighboring cells (up, down, left, right): For each direction:
Compute
new_row
andnew_col
. 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)
.If the new position is inside the grid, i.e,
0 <= new_row < n and 0 <= new_col < n
, and has not been visited yet (not in thevisited
set):Add the new cell to the heap:
(grid[new_row][new_col], new_row, new_col)
.Mark the new cell as visited by adding
(new_row, new_col)
to thevisited
set.
Let’s look at the following illustration to get a better understanding of the solution: