Swim in Rising Water

The key idea

You are not summing or counting a path — you are minimizing the maximum elevation you ever step on. The answer is the smallest value t such that the cells with elevation <= t connect the start to the goal. Grow outward from the start by always swimming into the lowest unvisited neighbor (a Dijkstra where the path cost is the running max, not a sum); the elevation of the cell that first lets you reach the corner is the answer.

Problem

You are given an n x n integer grid grid where grid[i][j] is the elevation of the cell at position (i, j).

It starts raining, and water gradually rises over time. At time t, the water level everywhere is t. You can swim from a cell to any 4-directionally adjacent cell, but only if the elevation of both the current cell and the destination cell is at most t. You can swim an unlimited distance in zero time, but you must stay within the bounds of the grid during your swim.

Starting from the top-left cell (0, 0), return the least time until you can reach the bottom-right cell (n - 1, n - 1).

Constraints

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n^2
Each value grid[i][j] is unique.

Examples

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

Complexity

Time: O(n^2 log n) Space: O(n^2)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →