Swim In Rising Water

Hard · Advanced Graphs

You are given an n by n grid where each cell holds a distinct elevation value from 0 to n*n - 1. Starting at the top left cell at time 0, you want to reach the bottom right cell. At time t you may move between two adjacent cells (up, down, left or right) only if both cells have elevation at most t, and you can wait at a cell for the water to rise without limit. Return the smallest time t at which a path of such moves from the top left cell to the bottom right cell exists.

Examples

Input:  grid = [[0,2],[1,3]]
Output: 3
Why:    At time 3 all cells with elevation <= 3 are submerged, opening a path from (0,0) to (1,1); no earlier time works because elevations 1 and 2 block the diagonal until time 3.

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
Why:    This spiral arrangement forces the water level to reach 16 before a continuous path of cells with elevation at most 16 connects the top left to the bottom right corner.

Input:  grid = [[3,2],[0,1]]
Output: 3
Why:    The starting cell itself has elevation 3, so the water level must already be at least 3 at time zero.

Constraints

1 <= n <= 50, grid is n x n, values are a permutation of 0..n*n-1

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Swim In Rising Water

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Swim In Rising Water. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.