179. Swim in Rising Water

Hard · Graph

You are given an `n x n` integer grid where `grid[i][j]` represents the elevation at cell `(i, j)`. Rain starts falling and at time `t`, the water level is `t`. You can swim from one cell to an adjacent cell (up, down, left, right) if both cells have elevation **at most** `t`.

Starting from the top-left cell `(0, 0)`, find the minimum time `t` such that there is a path from `(0, 0)` to the bottom-right cell `(n-1, n-1)`. You may assume that `grid[0][0]` and `grid[n-1][n-1]` are distinct values and that every value in the grid is unique and in the range `[0, n*n - 1]`.

Return the minimum time `t` needed to reach the bottom-right corner.

Examples

Example 1
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation: At time t=3, all cells have elevation ≤ 3. The path (0,0) → (0,1) → (1,1) is valid since max elevation along the path is max(0,2,3)=3. At t=2, cell (1,1) has elevation 3 > 2, so we can't reach it.
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 optimal path spirals around the grid. The bottleneck elevation along the best path is 16, so t=16 is the minimum time needed.

Constraints