Swim in Rising Water

Hard~35 min

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 is at most t.

You start at the top-left square (0, 0). Return the least time until you can reach the bottom-right square (n - 1, n - 1).

You can swim infinitely fast (moving between squares takes no time). You are simply waiting for the water to rise high enough.

Examples

Example 1

Input: grid = [[0,2],[1,3]]

Output: 3

Explanation: At time 3, the water level is 3 so all squares are accessible. The path (0,0) -> (1,0) -> (1,1) is available at time 3.

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 follows the perimeter: (0,0) -> (0,1) -> ... -> (0,4) -> (1,4) -> ... -> (4,4). The maximum elevation along this path is 16.

Constraints

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n^2
Each value in grid is unique
grid[0][0] and grid[n-1][n-1] are not necessarily 0 or n*n - 1
Expected time complexity: O(n² log n)

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run