Skip to main content
Talentd

Swim in Rising Water - Solution & Explanation

HardArrayBinary SearchDepth-First SearchBreadth-First Search26 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

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.length
  • n == grid[i].length
  • 1 <= n <= 50
  • 0 <= grid[i][j] < n2
  • Each value grid[i][j] is unique.

Approach Overview

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.

Approach 1: Approach 1: Dijkstra's Algorithm with Min-Heap

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Binary Search with DFS

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Union Find

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n^2), to maintain the priority queue and visited array.

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.
Space Complexity: O(n^2), due to the recursive stack and visitation array.

Union Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dijkstra's Algorithm with Min-HeapO(n^2 log n)O(n^2)Best general solution for grid path problems with weighted constraints
Binary Search + DFS/BFSO(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

Video Solution

Swim in Rising Water - Dijkstra's Algorithm - Leetcode 778 - Python • NeetCode • 85,522 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Swim in Rising Water easy or hard?
Swim in Rising Water is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that the grid traversal must minimize the maximum elevation along the path, which requires algorithms like Dijkstra, binary search with DFS, or Union Find.
How to solve Swim in Rising Water in O(n)?
An O(n) solution is not possible because the grid contains n^2 cells and at least most of them must be examined. The best known solutions run in O(n^2 log n) using a priority queue (Dijkstra) or binary search combined with DFS/BFS reachability checks.
Swim in Rising Water Python or Java solution?
The problem is commonly implemented using a priority queue in Python (heapq) or Java (PriorityQueue). Both implementations follow the same idea: push grid cells into a min-heap and track the maximum elevation seen along the path until the destination is reached.
What is the best approach for Swim in Rising Water?
Dijkstra's algorithm with a min-heap is the most common optimal approach. Treat each grid cell as a node and always expand the cell with the smallest elevation using a priority queue. The first time you reach the bottom-right cell, the maximum elevation along that path is the minimum time required. This runs in O(n^2 log n) time.
What data structure is used in Swim in Rising Water?
The primary data structure is a min-heap (priority queue) used in Dijkstra's algorithm to process cells in increasing elevation order. Other supporting structures include a visited matrix and optionally DFS/BFS stacks or queues when using the binary search approach.
What is the time complexity of Swim in Rising Water?
The optimal solutions typically run in O(n^2 log n) time for an n x n grid. Dijkstra's algorithm performs heap operations for up to n^2 cells, while Binary Search with DFS checks reachability in O(n^2) time across O(log n) iterations.
Is Swim in Rising Water asked at Google or Amazon interviews?
Swim in Rising Water is a well-known hard grid and graph problem that appears in high-level technical interviews. Variants involving priority queues, grid traversal, or minimum maximum path problems are commonly asked at companies like Google, Amazon, and Meta.

Ready to solve this problem?

Practice Swim in Rising Water with our built-in code editor and test cases.

Practice on FleetCode
Previous

Path With Minimum Effort