Skip to content
BASA DSA

Swim In Rising Water

HardAdvanced Graphs

At time t you may enter grid cells with elevation <= t. Return the smallest t allowing an orthogonal path from top-left to bottom-right.

Example 1

0,00
0,12
1,01
1,13
Cells show elevations. Start at top left; destination is bottom right. Move horizontally or vertically when the water level permits.
Input
grid = [[0,2],[1,3]]
Output
3

Explanation

Destination elevation 3 forces time at least 3, and a path exists by that time.

Example 2

0,00
Cells show elevations. Start at top left; destination is bottom right. Move horizontally or vertically when the water level permits.
Input
grid = [[0]]
Output
0

Explanation

Start and finish are the same elevation-zero cell.

Example 3

0,00
0,11
0,22
1,05
1,14
1,23
2,06
2,17
2,28
Cells show elevations. Start at top left; destination is bottom right. Move horizontally or vertically when the water level permits.
Input
grid = [[0,1,2],[5,4,3],[6,7,8]]
Output
8

Explanation

Destination elevation 8 is a lower bound; time 8 makes the whole grid traversable.

Constraints

  • Grid is n by n with 1 <= n <= 50
  • Elevations are a permutation of 0..n*n-1

Function contractswimInWaterArguments: json
Loading draft…
SolutionRuns on your device