Swim in Rising Water
Part of Practice: Hard Path Structures
You are given an n x n grid where grid[r][c] is the elevation of that cell, and all elevations are distinct values from 0 to n*n - 1. Rain raises the water level by 1 each time unit; at time t you can stand on any cell with elevation at most t, and you can move up/down/left/right between covered cells instantly. Starting on the top-left cell, return the earliest time you can reach the bottom-right cell.
Put differently: over all paths from corner to corner, find the one whose highest cell is as low as possible — that highest cell's elevation is the answer.
Examples
- Input:
- grid = [[0,2],[1,3]]
- Output:
- 3
Every route to the bottom-right must end on the cell with elevation 3, so you must wait until time 3 no matter what.
- 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
The snake-shaped path along the outer values 0..6 is blocked by 24..21, so the best route's tallest cell is 16.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.