Swim in Rising Water
Swim in Rising Water is a hard graphs problem solved with the dijkstra pattern.
The best approach, optimal (dijkstra on the maximum elevation), runs in O(n² log n) time and O(n²) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every time) up.
Problem
You are given an n x n grid where grid[i][j] is the elevation of cell (i, j); all elevations are distinct numbers from 0 to n² - 1. Rain starts falling, and at time t the water level everywhere is t.
You start at the top-left cell (0, 0). At time t you may swim from a cell to any of its four neighbours, instantly and as far as you like, as long as both cells have elevation at most t. Return the earliest time at which you can reach the bottom-right cell (n - 1, n - 1).
Examples
Example 1
- Input
grid = [[0, 3], [1, 2]]- Output
2- Why
- Go down to 1 and then right to 2. Nothing higher than 2 is touched, and the target itself is 2.
Example 2
- Input
grid = [[0, 5, 4], [8, 7, 3], [1, 2, 6]]- Output
6- Why
- The route 0 -> 5 -> 4 -> 3 -> 6 never climbs above 6, and every route must end on the 6 anyway.
Example 3
- Input
grid = [[3, 1, 6], [0, 8, 2], [4, 7, 5]]- Output
6- Why
- Going along the top and down the right side, 3 -> 1 -> 6 -> 2 -> 5, peaks at 6; the left-side route through 0, 4, 7 would need time 7.
Constraints
n == grid.length == grid[i].length1 <= n <= 500 <= grid[i][j] < n², and all values in the grid are distinct.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every time) | O(n⁴) | O(n²) |
| Better (binary search on time + BFS) | O(n² log n) | O(n²) |
| Optimal (Dijkstra on the maximum elevation) | O(n² log n) | O(n²) |
1Brute force (try every time)
O(n⁴)Up to n² values of t, each with a BFS over n² cells.O(n²)The visited array and queue of one BFS.Try t = 0, 1, 2, ... in order. For each t, run a BFS from (0, 0) that only steps onto cells with elevation <= t. The first t for which the target is reached is the answer.
- For t from max(grid[0][0], grid[n-1][n-1]) up to n² - 1:
- BFS from (0, 0) over 4-directional neighbours with elevation <= t.
- If (n - 1, n - 1) was visited, return t.
class Solution {
private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
public int swimInWater(int[][] grid) {
int n = grid.length;
for (int t = Math.max(grid[0][0], grid[n - 1][n - 1]); ; t++) {
if (canReach(grid, t)) return t;
}
}
private boolean canReach(int[][] grid, int t) {
int n = grid.length;
boolean[][] seen = new boolean[n][n];
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[] { 0, 0 });
seen[0][0] = true;
while (!q.isEmpty()) {
int[] c = q.poll();
if (c[0] == n - 1 && c[1] == n - 1) return true;
for (int[] d : DIRS) {
int r = c[0] + d[0], col = c[1] + d[1];
if (r >= 0 && r < n && col >= 0 && col < n && !seen[r][col] && grid[r][col] <= t) {
seen[r][col] = true;
q.add(new int[] { r, col });
}
}
}
return false;
}
}class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
def can_reach(t: int) -> bool:
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
q = deque([(0, 0)])
while q:
r, c = q.popleft()
if r == n - 1 and c == n - 1:
return True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
q.append((nr, nc))
return False
t = max(grid[0][0], grid[n - 1][n - 1])
while not can_reach(t):
t += 1
return tclass Solution {
bool canReach(vector<vector<int>>& grid, int t) {
int n = grid.size();
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<vector<bool>> seen(n, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push({0, 0});
seen[0][0] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == n - 1 && c == n - 1) return true;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) {
seen[nr][nc] = true;
q.push({nr, nc});
}
}
}
return false;
}
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
int t = max(grid[0][0], grid[n - 1][n - 1]);
while (!canReach(grid, t)) t++;
return t;
}
};function swimInWater(grid) {
const n = grid.length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const canReach = (t) => {
const seen = Array.from({ length: n }, () => new Array(n).fill(false));
seen[0][0] = true;
const q = [[0, 0]];
for (let head = 0; head < q.length; head++) {
const [r, c] = q[head];
if (r === n - 1 && c === n - 1) return true;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) {
seen[nr][nc] = true;
q.push([nr, nc]);
}
}
}
return false;
};
let t = Math.max(grid[0][0], grid[n - 1][n - 1]);
while (!canReach(t)) t++;
return t;
}2Better (binary search on time + BFS)
O(n² log n)About log(n²) BFS runs, each O(n²).O(n²)Visited array and queue for one BFS.Reachability only improves as t grows, so the predicate "the target is reachable at time t" is monotone. Binary search the smallest t in [max(start, target), n² - 1] and test each guess with a BFS.
- lo = max(grid[0][0], grid[n-1][n-1]), hi = n² - 1.
- While lo < hi: mid = (lo + hi) / 2; if BFS at mid reaches the target, hi = mid, else lo = mid + 1.
- Return lo.
class Solution {
private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
public int swimInWater(int[][] grid) {
int n = grid.length;
int lo = Math.max(grid[0][0], grid[n - 1][n - 1]), hi = n * n - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (canReach(grid, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
private boolean canReach(int[][] grid, int t) {
int n = grid.length;
boolean[][] seen = new boolean[n][n];
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[] { 0, 0 });
seen[0][0] = true;
while (!q.isEmpty()) {
int[] c = q.poll();
if (c[0] == n - 1 && c[1] == n - 1) return true;
for (int[] d : DIRS) {
int r = c[0] + d[0], col = c[1] + d[1];
if (r >= 0 && r < n && col >= 0 && col < n && !seen[r][col] && grid[r][col] <= t) {
seen[r][col] = true;
q.add(new int[] { r, col });
}
}
}
return false;
}
}class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
def can_reach(t: int) -> bool:
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
q = deque([(0, 0)])
while q:
r, c = q.popleft()
if r == n - 1 and c == n - 1:
return True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
q.append((nr, nc))
return False
lo, hi = max(grid[0][0], grid[n - 1][n - 1]), n * n - 1
while lo < hi:
mid = (lo + hi) // 2
if can_reach(mid):
hi = mid
else:
lo = mid + 1
return loclass Solution {
bool canReach(vector<vector<int>>& grid, int t) {
int n = grid.size();
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<vector<bool>> seen(n, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push({0, 0});
seen[0][0] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == n - 1 && c == n - 1) return true;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) {
seen[nr][nc] = true;
q.push({nr, nc});
}
}
}
return false;
}
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
int lo = max(grid[0][0], grid[n - 1][n - 1]), hi = n * n - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (canReach(grid, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
};function swimInWater(grid) {
const n = grid.length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const canReach = (t) => {
const seen = Array.from({ length: n }, () => new Array(n).fill(false));
seen[0][0] = true;
const q = [[0, 0]];
for (let head = 0; head < q.length; head++) {
const [r, c] = q[head];
if (r === n - 1 && c === n - 1) return true;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) {
seen[nr][nc] = true;
q.push([nr, nc]);
}
}
}
return false;
};
let lo = Math.max(grid[0][0], grid[n - 1][n - 1]), hi = n * n - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (canReach(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}3Optimal (Dijkstra on the maximum elevation)
O(n² log n)Each of the n² cells enters and leaves the heap once, at O(log n²) each.O(n²)Visited array and heap.Treat the cost of a path as the highest elevation on it. Starting from (0, 0), repeatedly pop the frontier cell with the lowest elevation from a min-heap, raise a running maximum to that elevation, and push its unvisited neighbours. Because the heap always grows the reachable region through the lowest possible cell, the running maximum when the target is popped is the minimum time.
- Push (grid[0][0], 0, 0) and mark (0, 0) visited; set best = 0.
- Pop the smallest cell; best = max(best, its elevation).
- If it is (n - 1, n - 1), return best.
- Push every unvisited neighbour and mark it visited.
class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
boolean[][] seen = new boolean[n][n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[] { grid[0][0], 0, 0 });
seen[0][0] = true;
int best = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
best = Math.max(best, cur[0]);
if (cur[1] == n - 1 && cur[2] == n - 1) return best;
for (int[] d : dirs) {
int r = cur[1] + d[0], c = cur[2] + d[1];
if (r >= 0 && r < n && c >= 0 && c < n && !seen[r][c]) {
seen[r][c] = true;
pq.offer(new int[] { grid[r][c], r, c });
}
}
}
return best;
}
}class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
heap = [(grid[0][0], 0, 0)]
best = 0
while heap:
h, r, c = heapq.heappop(heap)
best = max(best, h)
if r == n - 1 and c == n - 1:
return best
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
seen[nr][nc] = True
heapq.heappush(heap, (grid[nr][nc], nr, nc))
return bestclass Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<vector<bool>> seen(n, vector<bool>(n, false));
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
pq.push({grid[0][0], 0, 0});
seen[0][0] = true;
int best = 0;
while (!pq.empty()) {
auto [h, r, c] = pq.top();
pq.pop();
best = max(best, h);
if (r == n - 1 && c == n - 1) return best;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc]) {
seen[nr][nc] = true;
pq.push({grid[nr][nc], nr, nc});
}
}
}
return best;
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
isEmpty() { return this.a.length === 0; }
peek() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function swimInWater(grid) {
const n = grid.length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const seen = Array.from({ length: n }, () => new Array(n).fill(false));
const pq = new MinHeap((a, b) => a[0] - b[0]);
pq.push([grid[0][0], 0, 0]);
seen[0][0] = true;
let best = 0;
while (!pq.isEmpty()) {
const [h, r, c] = pq.pop();
best = Math.max(best, h);
if (r === n - 1 && c === n - 1) return best;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc]) {
seen[nr][nc] = true;
pq.push([grid[nr][nc], nr, nc]);
}
}
}
return best;
}Edge cases to test
- A 1 x 1 grid: the answer is the single value
- The start cell or the target cell holds the largest value on the best route
- The best route winds around a ridge instead of going straight
Hints
Hint 1
At time t you can stand on exactly the cells with elevation <= t. The answer is the smallest t for which the start and target are connected through such cells.
Hint 2
Being reachable at time t implies being reachable at t + 1, so you can binary search on t and run a BFS for each guess.
Hint 3
Even better: run Dijkstra where the cost of a path is the largest elevation on it. Always expand the reachable cell with the lowest elevation using a min-heap; when you pop the target, the running maximum is the answer.
FAQ
What is the best time complexity for Swim in Rising Water?
Optimal (Dijkstra on the maximum elevation) runs in O(n² log n) time and O(n²) extra space. Each of the n² cells enters and leaves the heap once, at O(log n²) each.
Which pattern does Swim in Rising Water use?
It is a graphs problem that uses the dijkstra pattern. Other problems with the same pattern: Network Delay Time, Find the City With the Smallest Number of Neighbors at a Threshold Distance, Cheapest Flights Within K Stops.
Is there a brute force solution for Swim in Rising Water?
Yes. Brute force (try every time) takes O(n⁴) time and O(n²) space. Try t = 0, 1, 2, ...
Which edge cases should I test for Swim in Rising Water?
A 1 x 1 grid: the answer is the single value; The start cell or the target cell holds the largest value on the best route; The best route winds around a ridge instead of going straight.