Swim in Rising Water
Problem Description
You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
It starts raining, and water gradually rises over time. At time t, the water level is t, meaning any cell with elevation less than equal to t is submerged or reachable.
You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.
Return the minimum time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).
Example 1:
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
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 final route is shown. We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 500 <= grid[i][j] < n2- Each value
grid[i][j]is unique.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The first approach is a brute force method, where we simulate the water level increasing over time and check if a path exists from the top-left to the bottom-right of the grid for each water level. This approach can be implemented using a BFS or DFS to explore the reachability of the target cell at each possible water level.
Steps:
- Start iterating over water levels from 0 to the maximum possible water level in the grid.
- For each water level, use a BFS or DFS to determine if there is a path from the top-left corner to the bottom-right corner where all visited cells are less than or equal to the current water level.
- The first water level at which a path exists is the minimum time required to swim from the top left to the bottom right of the grid.
Code:
- Time Complexity: O(N^4), where N is the edge length of the grid. This is because we check each water level separately and perform a graph search on an N x N grid.
- Space Complexity: O(N^2) for the visited matrix and the queue used in BFS.
2. Binary Search with BFS/DFS
Intuition:
This approach improves upon the brute force method by applying binary search on the possible time value. For each middle value, we determine if the path can be formed using BFS/DFS as before. This significantly reduces the time complexity since we're not iterating through every possible water level but rather narrowing down the possibilities using binary search.
Steps:
- Use binary search to find the minimum time required for the water level so a path exists.
- For a middle point in the binary search range, use BFS/DFS to check for path existence.
- Adjust the binary search range based on whether a path was successful or blocked.
Code:
- Time Complexity: O(N^2 * log(MaxVal)), where MaxVal is the maximum value (N * N - 1).
- Space Complexity: O(N^2) for visited structures.
3. Dijkstra's Algorithm
Intuition:
The optimal approach for this problem is to use a priority queue (min-heap) to simulate Dijkstra's algorithm, which efficiently finds the minimum-path to the destination as the constraints evolve. Here, the priority queue helps in efficiently computing which cell to visit next based on the minimum possible water level encountered on the path.
Steps:
- Use a priority queue to store cells along with their corresponding water level, starting from the top-left corner.
- At each step, pop the least val cell from the queue, and mark it visited.
- Push neighboring cells into the queue only if they are not visited.
- Track the maximum water level on the current path, and if you reach the target cell (bottom-right), return that value as the result.
Code:
- Time Complexity: O(N^2 * log(N)), where N is the number of cells. The priority queue operations are logarithmic.
- Space Complexity: O(N^2) for visited structures and the priority queue storage.