Swim in Rising Water
Description
You are given an n × n integer matrix grid where each value grid[i][j] represents the elevation at position (i, j).
Rain begins falling at time 0, and the water level across the entire grid rises uniformly — at time t, the water level is exactly t. A cell is accessible (you can stand on it or swim through it) if and only if its elevation is less than or equal to the current water level t.
You can swim from one cell to any 4-directionally adjacent cell (up, down, left, right) as long as both cells have elevation at most t. Swimming any distance takes zero time — the only constraint is that both the source and destination cells must be submerged at the current time.
Starting from the top-left corner (0, 0), find and return the minimum time t at which you can reach the bottom-right corner (n - 1, n - 1).
Examples
Example 1
Input: grid = [[0, 2], [1, 3]]
Output: 3
Explanation: At time t=0, only cell (0,0) with elevation 0 is accessible — you cannot move anywhere. At t=1, cells (0,0) and (1,0) are accessible, but (1,1) still requires elevation 3. At t=2, you can also reach (0,1), but (1,1) is still blocked. Only at t=3 does the water level reach 3, making all cells accessible and allowing you to swim from (0,0) to (1,1).
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 optimal path follows the spiral of low-elevation cells around the perimeter: (0,0)→(0,1)→(0,2)→(0,3)→(0,4)→(1,4)→(2,4)→(2,3)→(2,2)→(2,1)→(2,0)→(3,0)→(4,0)→(4,1)→(4,2)→(4,3)→(4,4). The maximum elevation on this path is 16 at cell (2,4), so we must wait until t=16.
Example 3
Input: grid = [[0, 3], [2, 1]]
Output: 2
Explanation: At t=2, cells with elevation ≤ 2 are: (0,0)=0, (1,0)=2, and (1,1)=1. The path (0,0)→(1,0)→(1,1) uses only these cells. The maximum elevation on the path is 2, so we do not need to wait for cell (0,1)=3 to become accessible. This shows that the answer depends on the best path, not the worst cell in the grid.
Constraints
- n == grid.length == grid[i].length
- 1 ≤ n ≤ 50
- 0 ≤ grid[i][j] < n²
- Each value grid[i][j] is unique (the grid is a permutation of 0 to n²-1)
Editorial
Brute Force
Intuition
Imagine you are standing on a hilltop and floodwaters are slowly rising around you. You want to reach the opposite corner of the terrain. At each minute, the water rises one unit, making more ground passable.
The most direct approach is to simply wait and check: at time 0, can you reach the destination? If not, wait until time 1 and check again. Keep waiting and checking until you find the earliest time that allows a complete path.
For each time level t (starting from 0), we run a breadth-first search (BFS) from (0, 0). During the BFS, we only visit cells whose elevation is at most t. If the BFS reaches (n-1, n-1), then t is our answer. If not, we increment t and try again.
This approach is guaranteed to find the minimum time because we try time levels in increasing order and stop at the first success.
Step-by-Step Explanation
Let's trace through with grid = [[0, 2], [1, 3]]:
Step 1: Initialize. Grid has elevations: (0,0)=0, (0,1)=2, (1,0)=1, (1,1)=3. We will try each time level starting from t=0.
Step 2: Try t=0. Only cells with elevation ≤ 0 are accessible: just (0,0)=0.
Step 3: BFS from (0,0) at t=0. Neighbors (0,1)=2 and (1,0)=1 both exceed 0. We are stuck at the start. No path to (1,1).
Step 4: Try t=1. Cells with elevation ≤ 1: (0,0)=0 and (1,0)=1. Two cells now accessible.
Step 5: BFS from (0,0) at t=1. Swim to (1,0). From (1,0), neighbor (1,1)=3 exceeds 1. Dead end. No path.
Step 6: Try t=2. Cells with elevation ≤ 2: (0,0)=0, (0,1)=2, (1,0)=1. Three cells accessible.
Step 7: BFS from (0,0) at t=2. Reach (0,1) and (1,0). From both, (1,1)=3 exceeds 2. Still blocked.
Step 8: Try t=3. All four cells have elevation ≤ 3. The entire grid is accessible.
Step 9: BFS from (0,0) at t=3. Path found: (0,0) → (1,0) → (1,1). All cells on path have elevation ≤ 3.
Step 10: Return 3. This is the minimum time to reach the destination.
Brute Force — Trying Every Time Level — Watch how the brute force approach tries each time level from 0 upward, running BFS at each level until a valid path to the destination is found.
Algorithm
- For each time level t from 0 to n² - 1:
a. If grid[0][0] > t or grid[n-1][n-1] > t, skip (start or end not accessible)
b. Run BFS from (0, 0), only visiting cells with elevation ≤ t
c. If BFS reaches (n-1, n-1), return t - Return n² - 1 (worst case: must wait for the highest elevation)
Code
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
for (int t = 0; t < n * n; t++) {
if (grid[0][0] > t || grid[n-1][n-1] > t) continue;
vector<vector<bool>> visited(n, vector<bool>(n, false));
queue<pair<int,int>> q;
q.push({0, 0});
visited[0][0] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == n-1 && c == n-1) return t;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& !visited[nr][nc] && grid[nr][nc] <= t) {
visited[nr][nc] = true;
q.push({nr, nc});
}
}
}
}
return n * n - 1;
}
};class Solution:
def swimInWater(self, grid: list[list[int]]) -> int:
from collections import deque
n = len(grid)
for t in range(n * n):
if grid[0][0] > t or grid[n - 1][n - 1] > t:
continue
visited = [[False] * n for _ in range(n)]
queue = deque([(0, 0)])
visited[0][0] = True
while queue:
r, c = queue.popleft()
if r == n - 1 and c == n - 1:
return t
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] <= t:
visited[nr][nc] = True
queue.append((nr, nc))
return n * n - 1class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (int t = 0; t < n * n; t++) {
if (grid[0][0] > t || grid[n-1][n-1] > t) continue;
boolean[][] visited = new boolean[n][n];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
visited[0][0] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
if (r == n-1 && c == n-1) return t;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& !visited[nr][nc] && grid[nr][nc] <= t) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
}
return n * n - 1;
}
}Complexity Analysis
Time Complexity: O(n⁴)
We iterate over up to n² possible time values. For each time value, we run a BFS that visits up to n² cells, with each cell processed in O(1) time. The total work is O(n²) time values × O(n²) BFS work = O(n⁴). For n=50, this is roughly 6.25 million operations.
Space Complexity: O(n²)
The BFS uses a visited array of size n² and a queue that can hold at most n² cells. Both are recreated for each time level but only one exists at a time.
Why This Approach Is Not Efficient
The brute force tries every possible time value t from 0 to n²-1 sequentially, running a full BFS traversal at each level. With n up to 50, the grid has up to 2,500 cells, and we might try up to 2,500 time values. Each BFS costs O(n²), giving O(n⁴) total — roughly 6.25 million operations for n=50. While this fits within typical time limits, it is unnecessarily wasteful.
The core inefficiency is that we try every time value one by one. But there is a crucial monotonic property: if a path exists at time t, it also exists at any time t' > t, because a higher water level only makes more cells accessible, never fewer. This means the answer creates a clear boundary — all times below it fail, and all times at or above it succeed.
Whenever we have a yes/no question with a monotonic boundary, binary search is the natural tool. Instead of checking every time level linearly, we can jump to the middle of the range and eliminate half the possibilities with each BFS call.
Better Approach - Binary Search on Answer
Intuition
The brute force checks time levels t = 0, 1, 2, 3, ... one at a time. But we noticed the monotonic property: once a path becomes possible at time t, it remains possible for all future times.
This is exactly the setup for binary search on the answer. We define a search range [low, high] where low = 0 and high = n² - 1. At each step:
- Compute mid = (low + high) / 2
- Run BFS to check: is there a path at time t = mid?
- If YES → the answer is mid or earlier, so set high = mid
- If NO → the answer must be later, so set low = mid + 1
When low equals high, we have found the exact minimum time.
This reduces the number of BFS calls from O(n²) in the brute force to O(log(n²)) = O(2 log n), a dramatic improvement.
Step-by-Step Explanation
Let's trace through with grid = [[0, 2], [1, 3]]:
Step 1: Initialize binary search: low = 0, high = n² - 1 = 3.
Step 2: Compute mid = (0 + 3) / 2 = 1. Run BFS to check if a path exists at t=1.
Step 3: BFS at t=1: cells with elevation ≤ 1 are (0,0)=0 and (1,0)=1. From (0,0), swim to (1,0). From (1,0), (1,1)=3 > 1 — blocked. No path.
Step 4: Path not found at t=1. Set low = mid + 1 = 2. Search range narrows to [2, 3].
Step 5: Compute mid = (2 + 3) / 2 = 2. Run BFS at t=2.
Step 6: BFS at t=2: cells ≤ 2 are (0,0)=0, (0,1)=2, (1,0)=1. Reach all three, but (1,1)=3 > 2. Still blocked.
Step 7: Path not found at t=2. Set low = mid + 1 = 3. Now low = high = 3.
Step 8: Binary search converged. At t=3, all cells are accessible and a path exists.
Step 9: Return 3. Binary search needed only 2 BFS calls instead of 4.
Binary Search on Answer — Halving the Time Range — Watch how binary search eliminates half the possible time values at each step, needing far fewer BFS calls than brute force to find the minimum time.
Algorithm
- Set low = 0, high = n² - 1
- While low < high:
a. Compute mid = (low + high) / 2
b. Run BFS from (0,0) using only cells with elevation ≤ mid
c. If BFS reaches (n-1, n-1): set high = mid (answer could be mid or smaller)
d. If BFS fails: set low = mid + 1 (answer must be larger) - Return low (which equals high)
Optimization: The lower bound can be set to max(grid[0][0], grid[n-1][n-1]) since both the start and end cells must be accessible.
Code
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
auto canReach = [&](int t) -> bool {
if (grid[0][0] > t || grid[n-1][n-1] > t) return false;
vector<vector<bool>> visited(n, vector<bool>(n, false));
queue<pair<int,int>> q;
q.push({0, 0});
visited[0][0] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == n-1 && c == n-1) return true;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& !visited[nr][nc] && grid[nr][nc] <= t) {
visited[nr][nc] = true;
q.push({nr, nc});
}
}
}
return false;
};
int low = 0, high = n * n - 1;
while (low < high) {
int mid = (low + high) / 2;
if (canReach(mid)) high = mid;
else low = mid + 1;
}
return low;
}
};class Solution:
def swimInWater(self, grid: list[list[int]]) -> int:
from collections import deque
n = len(grid)
def can_reach(t):
if grid[0][0] > t or grid[n - 1][n - 1] > t:
return False
visited = [[False] * n for _ in range(n)]
queue = deque([(0, 0)])
visited[0][0] = True
while queue:
r, c = queue.popleft()
if r == n - 1 and c == n - 1:
return True
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] <= t:
visited[nr][nc] = True
queue.append((nr, nc))
return False
low, high = 0, n * n - 1
while low < high:
mid = (low + high) // 2
if can_reach(mid):
high = mid
else:
low = mid + 1
return lowclass Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
int low = 0, high = n * n - 1;
while (low < high) {
int mid = (low + high) / 2;
if (canReach(grid, n, mid)) high = mid;
else low = mid + 1;
}
return low;
}
private boolean canReach(int[][] grid, int n, int t) {
if (grid[0][0] > t || grid[n-1][n-1] > t) return false;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
boolean[][] visited = new boolean[n][n];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
visited[0][0] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
if (r == n-1 && c == n-1) return true;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& !visited[nr][nc] && grid[nr][nc] <= t) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
return false;
}
}Complexity Analysis
Time Complexity: O(n² log n)
The binary search runs O(log(n²)) = O(2 log n) = O(log n) iterations. Each iteration performs a BFS that visits up to n² cells in O(n²) time. Total: O(n² × log n). For n=50, this is roughly 2,500 × 6 ≈ 15,000 operations — vastly better than the brute force's 6.25 million.
Space Complexity: O(n²)
Each BFS call uses a visited array of size n² and a queue holding at most n² elements.
Why This Approach Is Not Efficient
Binary search on the answer reduces BFS calls from O(n²) to O(log n), bringing the total time down to O(n² log n). This is a major improvement over brute force.
However, binary search treats each BFS as an independent black box: "can we reach the destination at time t?" It discards all information gathered during one BFS when starting the next. Cells that were explored at t=5 are re-explored from scratch at t=8. This redundant work, while not affecting the asymptotic complexity, is conceptually wasteful.
A more elegant approach reframes the problem entirely. Instead of asking "what is the minimum time?", we ask: "what is the path from (0,0) to (n-1,n-1) that minimizes the maximum elevation along the way?" This is a modified shortest path problem where the 'distance' to a cell is the maximum elevation encountered to reach it. Dijkstra's algorithm solves this in a single pass — processing each cell exactly once, guided by a priority queue — with no redundant exploration.
Optimal Approach - Modified Dijkstra's Algorithm
Intuition
Instead of searching for the right time level, let us think about paths directly. The time you need to wait is determined by the highest peak you must cross on your path. If one path has a maximum elevation of 8, you wait until t=8. If another path has a maximum of 5, you only need t=5. We want the path that minimizes the maximum elevation.
This is a classic shortest path problem with an unusual distance metric: instead of summing edge weights, we take the maximum. The 'cost' of a path is the highest elevation on it, and we want to minimize this cost.
Dijkstra's algorithm is perfect for this. We use a min-heap (priority queue) where each entry is (max_elevation_so_far, row, col). At each step, we pop the cell with the lowest cost and explore its neighbors. For each neighbor, the new cost is max(current_cost, neighbor_elevation). If this is less than the previously known cost for that neighbor, we update it and push it into the heap.
The first time we pop the destination cell from the heap, we have the optimal answer — because the min-heap guarantees we always process the cheapest option first.
Step-by-Step Explanation
Let's trace through with grid = [[0, 2], [1, 3]]:
Step 1: Initialize a min-heap and distance table. Set dist[0][0] = grid[0][0] = 0, all others = ∞. Push (cost=0, row=0, col=0) into the heap.
Step 2: Pop (0, 0, 0) from the heap — lowest cost. Mark (0,0) as processed.
Step 3: Explore (0,0)'s neighbors. (0,1) has elevation 2: path cost = max(0, 2) = 2. (1,0) has elevation 1: path cost = max(0, 1) = 1. Both improve upon ∞. Push both into the heap.
Step 4: Pop (1, 1, 0) from the heap — cost 1 is the lowest available. Mark (1,0) as processed.
Step 5: Explore (1,0)'s neighbor (1,1): elevation 3, path cost = max(1, 3) = 3. Update dist[1][1] = 3 and push (3, 1, 1). (0,0) already processed.
Step 6: Pop (2, 0, 1) from the heap — cost 2 is next lowest. Mark (0,1) as processed.
Step 7: Explore (0,1)'s neighbor (1,1): path cost = max(2, 3) = 3. This equals the existing dist[1][1] = 3, so no improvement. Skip.
Step 8: Pop (3, 1, 1) from the heap. This is the destination (n-1, n-1)!
Step 9: Return 3. The optimal path is (0,0) → (1,0) → (1,1) with maximum elevation 3.
Modified Dijkstra's — Min-Heap Path Finding — Watch how Dijkstra's algorithm uses a priority queue to always expand the cheapest cell first, finding the path that minimizes the maximum elevation in a single pass.
Algorithm
- Create a distance table
dist[n][n]initialized to ∞, withdist[0][0] = grid[0][0] - Push
(grid[0][0], 0, 0)into a min-heap (priority queue ordered by cost) - While the heap is not empty:
a. Pop(maxElev, r, c)— the cell reachable with the lowest maximum elevation
b. If(r, c)is the destination(n-1, n-1), returnmaxElev
c. IfmaxElev > dist[r][c], skip (this is a stale entry)
d. For each 4-directional neighbor(nr, nc):- Compute
newDist = max(maxElev, grid[nr][nc]) - If
newDist < dist[nr][nc], updatedist[nr][nc] = newDistand push(newDist, nr, nc)
- Compute
- Return -1 (should not reach here for valid input)
Code
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
priority_queue<tuple<int,int,int>,
vector<tuple<int,int,int>>,
greater<>> pq;
dist[0][0] = grid[0][0];
pq.push({grid[0][0], 0, 0});
while (!pq.empty()) {
auto [maxElev, r, c] = pq.top();
pq.pop();
if (r == n-1 && c == n-1) return maxElev;
if (maxElev > dist[r][c]) continue;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
int newDist = max(maxElev, grid[nr][nc]);
if (newDist < dist[nr][nc]) {
dist[nr][nc] = newDist;
pq.push({newDist, nr, nc});
}
}
}
}
return -1;
}
};class Solution:
def swimInWater(self, grid: list[list[int]]) -> int:
import heapq
n = len(grid)
dist = [[float('inf')] * n for _ in range(n)]
dist[0][0] = grid[0][0]
heap = [(grid[0][0], 0, 0)]
while heap:
max_elev, r, c = heapq.heappop(heap)
if r == n - 1 and c == n - 1:
return max_elev
if max_elev > dist[r][c]:
continue
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n:
new_dist = max(max_elev, grid[nr][nc])
if new_dist < dist[nr][nc]:
dist[nr][nc] = new_dist
heapq.heappush(heap, (new_dist, nr, nc))
return -1class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
int[][] dist = new int[n][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = grid[0][0];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{grid[0][0], 0, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int maxElev = curr[0], r = curr[1], c = curr[2];
if (r == n-1 && c == n-1) return maxElev;
if (maxElev > dist[r][c]) continue;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
int newDist = Math.max(maxElev, grid[nr][nc]);
if (newDist < dist[nr][nc]) {
dist[nr][nc] = newDist;
pq.offer(new int[]{newDist, nr, nc});
}
}
}
}
return -1;
}
}Complexity Analysis
Time Complexity: O(n² log n)
Each of the n² cells is processed at most once by the priority queue. Each push/pop operation on the heap takes O(log(n²)) = O(2 log n) = O(log n) time. Total: n² cells × O(log n) per operation = O(n² log n). While this matches the binary search approach asymptotically, Dijkstra's often runs faster in practice because it processes each cell exactly once without restarting BFS.
Space Complexity: O(n²)
The distance table uses O(n²) space. The priority queue can hold at most O(n²) entries (one per cell in the worst case).