You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
The rain starts to fall. At time t, the depth of the water everywhere is t. 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 least 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] < n2grid[i][j] is unique.The key challenge in #778 Swim in Rising Water is finding the minimum time required to move from the top-left to the bottom-right cell of a grid where the water level gradually rises. Each cell represents an elevation, and you can only enter a cell when the water level is at least that height.
A common strategy is to treat the grid as a graph and apply a Dijkstra-like approach using a min-heap (priority queue). At each step, expand to the neighboring cell with the smallest elevation, ensuring the path minimizes the maximum elevation encountered so far. This effectively finds the earliest time you can reach the destination.
Another effective method uses binary search on the time value combined with BFS or DFS to check whether the destination is reachable at a given water level. Both strategies rely on careful traversal of the matrix while respecting elevation constraints. These approaches ensure efficient exploration of the grid.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Min-Heap / Dijkstra-style BFS | O(n^2 log n) | O(n^2) |
| Binary Search + BFS/DFS | O(n^2 log n) | O(n^2) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use either Dijkstra's, or binary search for the best time T for which you can reach the end if you only step on squares at most T.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is considered a classic hard-level grid and graph traversal question. Variants of it are commonly discussed in interviews at top tech companies because it combines graphs, heaps, and binary search concepts.
The most common optimal approach uses a Dijkstra-like traversal with a min-heap (priority queue). It always expands the cell with the smallest elevation first, minimizing the maximum height encountered along the path to the destination.
Yes, another approach is to binary search on the time value and check reachability using BFS or DFS. For each candidate time, you verify whether you can travel from the start to the end using only cells with elevation less than or equal to that time.
A priority queue (min-heap) is particularly effective because it allows you to always process the lowest elevation cell next. This mirrors the behavior of Dijkstra’s algorithm when minimizing the maximum edge cost along a path.