Swim in Rising Water

Hard

Topics
GraphBinary SearchHeapMatrix

You are given an n x n grid where grid[i][j] is the elevation at that cell. At time t the water level is t, and you can move between two adjacent cells if both elevations are at most t. Starting at the top-left, return the least time to reach the bottom-right.

Example 1

Input:  grid = [[0,2],[1,3]]
Output: 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

Constraints

  • 1 <= n <= 50
  • grid holds a permutation of 0 .. n^2 - 1
Run ⌘' · Submit ⌘⏎