Escape the Rising Flood
A valley is a grid where heights[r][c] is the ground height of each cell. Water starts rising at time 0, and at time t the water level is t. A rescue boat can be on a cell only when the water level is at least the cell's height, and it can move instantly between cells that share a side.
The boat starts at the top-left cell and must reach the bottom-right cell. Return the earliest time t at which this is possible. In other words, find a path whose highest cell is as low as possible and return that height.
Example 1
Input: heights = [[3,8,4],[6,9,2],[7,5,1]] Output: 7 Explanation: Down the left side: the highest cell on the way is 7.
Example 2
Input: heights = [[1,1,1],[9,9,1],[1,1,1]] Output: 1 Explanation: Along the top row and down the right column every cell is 1.
Constraints
- 1 <= rows, cols <= 150
- 0 <= heights[r][c] <= 10^5
Hint 1
This is a shortest-path problem where the cost of a path is its maximum height, not its sum.
Hint 2
Run Dijkstra with a min-heap: the time to reach a neighbour is max(current time, neighbour height).
Discussion 0
Join free to post in the discussion.
Good practice for: Game Developer, Backend Developer, Embedded Systems Engineer, Data Scientist, AI Engineer (LLM & Generative AI)
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.