Advanced Graphs Weighted shortest paths

474. Swim in Rising Water

You are given an n × n grid of heights, grid. grid[i][j] is the height of the cell in row i, column j.

Rain starts to fall. At time t, the water stands at height t everywhere, and a cell is under water when its height is at most t. You can swim from a cell to the cell directly above, below, left or right of it when both cells are under water. Swimming takes no time, however far you go.

You start in the top-left cell at time 0. Return the smallest time at which you can reach the bottom-right cell.

Example 1

Input: grid = [[5, 13, 8, 0, 4], [12, 6, 2, 19, 11], [20, 23, 21, 24, 1], [14, 17, 3, 16, 10], [7, 22, 15, 18, 9]]

Output: 12

Explanation: Both neighbours of the start are 12 or higher, so you cannot leave before time 12. At time 12, the path 5 → 12 → 6 → 2 → 8 → 0 → 4 → 11 → 1 → 10 → 9 is all under water. It goes back up to the top row on the way.

Example 2

Input: grid = [[7]]

Output: 7

Explanation: The start is also the end, but you can only be in it once the water has reached 7.

Example 3

Input: grid = [[4, 4, 1000000000], [1000000000, 4, 1000000000], [1000000000, 4, 4]]

Output: 4

Explanation: Heights can repeat. The cells of height 4 form a path from corner to corner, and it is under water at time 4.

Check your understanding

Work out the answer for this input before you write any code.

grid = [[5, 1], [2, 3]]

Constraints

n == grid.length == grid[i].length
1 ≤ n ≤ 300
0 ≤ grid[i][j] ≤ 10⁹

Clarifying questions

What you would ask an interviewer before writing any code.