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.Problem Overview: You are given an array-based n x n grid where each cell represents the elevation of the land. Water rises over time, and at time t you can only enter cells with elevation ≤ t. The goal is to reach the bottom-right cell from the top-left as early as possible.
Approach 1: Dijkstra's Algorithm with Min-Heap (Time: O(n2 log n), Space: O(n2))
This problem behaves like a shortest-path problem where the "cost" of a path is the maximum elevation encountered along the route. Use a min-heap (priority queue) to always expand the cell with the smallest elevation seen so far. Start from (0,0), push it into the heap, and repeatedly pop the lowest elevation cell. From each cell, explore its four neighbors and push them into the heap if they haven't been visited. The key insight: the moment you pop the destination cell, the maximum elevation along that path is the minimum time required. This works because Dijkstra always processes the smallest possible "time" first.
The running time is dominated by heap operations across at most n^2 cells, giving O(n^2 log n). A visited matrix tracks processed cells, requiring O(n^2) space.
Approach 2: Binary Search with DFS (Time: O(n2 log n), Space: O(n2))
Another perspective: instead of constructing the path directly, search for the minimum time t that makes the destination reachable. Use binary search over the time range from grid[0][0] to n^2 - 1. For each candidate time, run a DFS (or BFS) starting at (0,0) and only move to cells whose elevation is ≤ t. If the destination becomes reachable, reduce the search range; otherwise increase it.
The DFS explores at most n^2 cells per check. Binary search runs about log(n^2) iterations, producing overall complexity of O(n^2 log n). This approach is conceptually simple because it separates "reachability" from "time optimization".
Recommended for interviews: Dijkstra with a min-heap is the most commonly expected solution. It demonstrates understanding of priority queues and shortest-path reasoning on grids. Binary search + DFS is also strong because it shows problem transformation skills—turning a path problem into a monotonic feasibility check. Explaining both approaches clearly signals strong algorithmic thinking.
This approach uses Dijkstra's algorithm with a priority queue (min-heap) to find the shortest increasing path to the destination. Each cell in the grid can be thought of as a node, with the elevation as the cost of reaching that node. The priority in the queue is determined by the maximum elevation encountered on the path to that cell. We continuously pick the cell with the lowest elevation cost that can be reached, update the costs of its neighbors and repeat the process until we reach the target cell (n-1, n-1).
This solution implements Dijkstra's algorithm with a custom priority queue using a simple array. The array is sorted to always process the cell with the minimal 'time cost'. The priority queue stores nodes represented as a 'Point', defined by its position and the maximum time required to reach that cell. The sorting results in a straightforward simulation of a min-heap while iterating through possible paths to the target node. The algorithm continues until the destination is reached, ensuring the path guarantees the minimum water depth that needs to be overcome.
Time Complexity: O(n^2 log n), due to sorting the priority queue at each step, where n is the side length of the grid.
Space Complexity: O(n^2), to maintain the priority queue and visited array.
This approach leverages binary search in union with a Depth-First Search (optimized traversal) to find the minimal elevation at which it is possible to traverse from the start to the end point. By evaluating the middling water level and checking the feasibility of reaching the destination, the search efficiently pinpoints the boundary condition: the smallest time 't' needed to connect the top-left and bottom-right corners without breaking elevation conditions.
This code applies binary search over time 't', checking for each midpoint, using depth-first search, whether a viable path exists under that water elevation. It captures the minimal usable 't' as its result. It ensures linear evaluation bounding within constraints, searching for thresholds iteratively where it's impossible to continue path exploration.
Time Complexity: O(n^2 log n), where for each of the log n steps in binary search the DFS traverses O(n^2) nodes in the worst case.
Space Complexity: O(n^2), due to the recursive stack and visitation array.
We can map each position (i, j) to an ID id = i times n + j, and use a union-find data structure to maintain connected components.
First, we use a one-dimensional array hi to record the position ID corresponding to each height, i.e., hi[h] represents the position ID with height h.
Then we traverse from height 0 to height n^2 - 1. For each height t, we merge position hi[t] with its four adjacent positions that have heights not exceeding t. If after merging, position 0 and position n^2 - 1 are connected, then we have found the minimum time t, and we return t.
The time complexity is O(n^2 times log n) and the space complexity is O(n^2), where n is the side length of the matrix.
| Approach | Complexity |
|---|---|
| Approach 1: Dijkstra's Algorithm with Min-Heap | Time Complexity: O(n^2 log n), due to sorting the priority queue at each step, where n is the side length of the grid. |
| Approach 2: Binary Search with DFS | Time Complexity: O(n^2 log n), where for each of the log n steps in binary search the DFS traverses O(n^2) nodes in the worst case. |
| Union Find | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm with Min-Heap | O(n^2 log n) | O(n^2) | Best general solution for grid path problems with weighted constraints |
| Binary Search + DFS/BFS | O(n^2 log n) | O(n^2) | When the answer is monotonic and can be validated via reachability |
| Union Find (Disjoint Set) | O(n^2 log n) | O(n^2) | Useful when processing cells in increasing elevation order and merging components |
Swim in Rising Water - Dijkstra's Algorithm - Leetcode 778 - Python • NeetCode • 80,300 views views
Watch 9 more video solutions →Practice Swim in Rising Water with our built-in code editor and test cases.
Practice on FleetCode