At time t, you can swim between adjacent cells whose elevations are both at most t. Return the least time at which you can reach the bottom-right cell from the top-left.
Before you code
The time a route needs is the highest elevation on it. Minimize the maximum along a path: a bottleneck shortest path.
Hints
- Heap entries are
(highest so far, r, c), starting with the start cell's elevation. - Moving to a neighbor:
max(current, grid[nr][nc]). - The first time the target is popped, its value is the answer.
Production & complexity notes
When solving Swim in rising water on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Dijkstra's algorithm to reinforce the underlying pattern.
What it practices
Bottleneck costs in Dijkstra, from Dijkstra's algorithm.