501. Swim in Rising Water
You are given an n × n integer grid grid where grid[i][j] is the elevation of cell (i, j). The elevations are a permutation of 0 to n²−1 — every value appears exactly once.
Rain starts and the water level rises: at time t, every cell with elevation at most t is under water. You begin on the top-left cell (0, 0) and want to reach the bottom-right cell (n−1, n−1). You may swim between 4-directionally adjacent cells whenever both are under water; swimming costs no time, and you may wait in place as long as you like.
Return the earliest time t at which you can be standing on (n−1, n−1). Equivalently: over all paths from corner to corner, return the smallest possible value of the highest elevation on the path.
Example 1:
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation: The destination itself has elevation 3, so nothing can happen before t = 3. At t = 3 every cell is under water and you swim 0 → 1 → 3 (or 0 → 2 → 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
Explanation: The ridge of cells 21–24 walls off the direct route, so every path must pass through the cell with elevation 16 (or higher). Snaking along 0…5, then down through 16 and around the spiral reaches the corner with peak elevation 16.
Constraints:
- 1 ≤ n ≤ 50
- 0 ≤ grid[i][j] < n²
- The elevations are a permutation: every value in 0 … n²−1 appears exactly once.
Hints:
Waiting is free, so the clock only matters through one number: the highest cell your route ever touches. The question is really "minimize, over all corner-to-corner paths, the maximum elevation on the path" — a minimax path problem.
Reachability is monotone: if you can cross at time t, you can cross at t+1. Whenever a yes/no question is monotone in t, you can binary search t and answer each probe with a BFS/DFS that only steps on cells ≤ t.
Or raise the water yourself: process cells in increasing elevation, union each newly flooded cell with flooded neighbors, and stop the moment the two corners share a component — that elevation is the answer.
Or run a Dijkstra variant: always expand the lowest-elevation cell on the frontier, tracking cost = max(elevation so far). A min-heap gives the earliest crossing directly.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[0,2],[1,3]]
Expected output: 3