572. Rising Tide Swim
A lake is divided into an n x n square of stepping stones. grid[r][c] is the minute at which the stone at row r, column c becomes safe to stand on, and it stays safe from then on. A swimmer starts on the top-left stone (0, 0) and wants to reach the bottom-right stone (n-1, n-1).
From a stone she can step to any of the four side-adjacent stones, instantly, but only onto stones that are already safe at that moment; she can wait on a safe stone for as long as she likes. Both the starting stone and the target stone must be safe when she is on them.
Return the earliest minute by which the swimmer can complete a path from the start to the target. In other words, find the path whose largest grid value is as small as possible, and return that value. Expected complexity is O(n^2 log n) time and O(n^2) space.
Example 1
- Input:
- grid = [[2,9],[8,3]]
- Output:
- 8
- Explanation:
Going through the 8 needs minute 8, while going through the 9 needs minute 9, so the answer is 8.
Example 2
- Input:
- grid = [[0,5,1],[7,6,2],[9,3,4]]
- Output:
- 5
- Explanation:
The path 0, 5, 1, 2, 4 has maximum 5, and any path must leave the start through 5 or 7, so 5 is optimal.
Example 3
- Input:
- grid = [[7]]
- Output:
- 7
- Explanation:
A single stone is both start and target and becomes safe at minute 7.
Constraints
1 ≤ n ≤ 500, the grid isn x n0 ≤ grid[r][c] ≤ 106- Values may repeat.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n^2 log n)
- Space
- O(n^2)