Swim in Rising Water

Hard· Dijkstra· Grid

Problem

In an n x n grid, grid[i][j] is the elevation of each cell. At time t the water level is t, and you can move between adjacent cells only if both have elevation at most t. Return the earliest time you can travel from the top-left cell to the bottom-right cell.

Examples

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

Output: 3

The destination itself has elevation 3, so nothing earlier works.

Input: grid = [[0,1,2],[7,8,3],[6,5,4]]

Output: 4

Follow the border 0 -> 1 -> 2 -> 3 -> 4 and avoid the high middle cells.

Constraints

• 1 <= n <= 50
• 0 <= grid[i][j] < n^2
• All elevations are distinct

Hints & approach

Hint 1

The cost of a path is the maximum elevation along it, not the sum.

Hint 2

Minimize that maximum: a Dijkstra-style search where path cost is max(current, next cell).

Hint 3

Binary search on t with a reachability check also works.

Approachtry the hints first

Run a modified Dijkstra with a min-heap of (time, row, col), starting from (grid[0][0], 0, 0). Pop the cell with the smallest required time; if it is the destination, return that time. Otherwise push each unvisited neighbour with max(time, neighbour elevation). Because the path cost is monotone non-decreasing, the first time the destination is popped is optimal.

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

← PreviousWord Ladder Next →Critical Connections in a Network