HardNeetCode150ArrayDepth-First SearchBreadth-First SearchBinary SearchHeap (Priority Queue)MatrixUnion Find
Swim in Rising Water
Find minimum time to swim from (0,0) to (n-1,n-1).
Examples
Input
grid = [[0,2],[1,3]]
Output
3
Swim: (0,0) at t=0, (0,1) at t=2, (1,1) at t=3.
Constraints
- •
n == grid.length - •
1 <= n <= 50 - •
0 <= grid[r][c] < n^2 - •
All values unique
Approaches
Binary search on time.
CodeT: O(n^2 * log(n^2)) | S: O(n^2) BFS queue
Visit cells in time order.
CodeT: O(n^2 log(n^2)) | S: O(n^2) heap
Sort cells by time, union.
CodeT: O(n^2 log(n^2)) | S: O(n^2)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Binary Search + BFS | O(n^2 * log(n^2)) | O(n^2) BFS queue | Binary search on time. |
| Dijkstra / Min Heap | O(n^2 log(n^2)) | O(n^2) heap | Visit cells in time order. |
| Union Find + Sort | O(n^2 log(n^2)) | O(n^2) | Sort cells by time, union. |
Binary Search + BFS
T: O(n^2 * log(n^2))S: O(n^2) BFS queue
Binary search on time.
Dijkstra / Min Heap
T: O(n^2 log(n^2))S: O(n^2) heap
Visit cells in time order.
Union Find + Sort
T: O(n^2 log(n^2))S: O(n^2)
Sort cells by time, union.
Common Mistakes
Wrong binary search bounds
Not visiting in time order
Wrong direction