Log inSign up
hardLeetCodeNot Started

Swim in Rising Water

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

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 is at most t.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (n - 1, n - 1)?

Constraints:

  • n == grid.length == grid[i].length
  • 1 <= n <= 50
  • 0 <= grid[i][j] < n2
  • Each value grid[i][j] is unique.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate minimax threshold problems on 2D grids.
  • Implement Dijkstra's Algorithm with non-additive bottleneck relaxation.
  • Compare Binary Search on Answer (O(N2 log(N2))) vs. Dijkstra (O(N2 log N)).
  • Leverage the uniqueness of cell values for efficient bounds.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a question asks to reach a destination where passage through each cell requires a minimum threshold (water height, clearance, effort) and you want to minimize the highest threshold along the route, apply Modified Dijkstra or Binary Search on Answer + BFS.

1. DFS Path Enumeration with Pruning

Intuition

Explore all simple paths from (0, 0) to (n - 1, n - 1). Track the maximum cell value along the path. Maintain an array minTime[r][c] to prune any path whose current peak elevation exceeds the recorded minimum for that cell.

Algorithm

  1. Initialize minTime grid of size n × n with infinity, set minTime[0][0] = grid[0][0].
  2. Define dfs(r, c, currentMax):
  3. currentMax = max(currentMax, grid[r][c])
  4. If currentMax >= minTime[r][c], return.
  5. minTime[r][c] = currentMax.
  6. If r == n - 1 && c == n - 1, return.
  7. Explore 4 neighbors (nr, nc) and recurse.
  8. Return minTime[n - 1][n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6const int dr[] = {-1, 1, 0, 0};
7const int dc[] = {0, 0, -1, 1};
8
9void dfs(int r, int c, int currentMax, const std::vector<std::vector<int>>& grid, std::vector<std::vector<int>>& minTime) {
10 currentMax = std::max(currentMax, grid[r][c]);
11 if (currentMax >= minTime[r][c]) return;
12 minTime[r][c] = currentMax;
13
14 int n = grid.size();
15 if (r == n - 1 && c == n - 1) return;
16
17 for (int d = 0; d < 4; ++d) {
18 int nr = r + dr[d], nc = c + dc[d];
19 if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
20 dfs(nr, nc, currentMax, grid, minTime);
21 }
22 }
23}
24
25int swimInWaterDFS(std::vector<std::vector<int>>& grid) {
26 int n = grid.size();
27 std::vector<std::vector<int>> minTime(n, std::vector<int>(n, INT_MAX));
28 dfs(0, 0, grid[0][0], grid, minTime);
29 return minTime[n - 1][n - 1];
30}
31
32int main() {
33 std::vector<std::vector<int>> grid = {{0, 2}, {1, 3}};
34 std::cout << "Swim in Water (DFS): " << swimInWaterDFS(grid) << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(4^(N^2)) worst case without aggressive pruning.
  • Space complexity: O(N^2) for the recursion stack and minTime grid.

2. Binary Search on Answer + BFS

Intuition

Water level is monotonically bounded between 0 and N2 - 1. If water level T allows swimming from (0, 0) to (n-1, n-1), then any level T' > T also allows it. We binary search for T. At each step, test if a path exists using only cells with grid[r][c] <= T via standard BFS.

Algorithm

  1. Initialize low = max(grid[0][0], grid[n-1][n-1]), high = n * n - 1, ans = high.
  2. While low <= high:
  3. mid = (low + high) / 2
  4. Run BFS from (0, 0) only traversing cells where grid[nr][nc] <= mid.
  5. If destination (n-1, n-1) is reached:
  6. ans = mid, high = mid - 1
  7. Else:
  8. low = mid + 1
  9. Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6bool canSwim(int t, const std::vector<std::vector<int>>& grid) {
7 int n = grid.size();
8 if (grid[0][0] > t || grid[n - 1][n - 1] > t) return false;
9
10 std::vector<std::vector<bool>> visited(n, std::vector<bool>(n, false));
11 std::queue<std::pair<int, int>> q;
12 q.push({0, 0});
13 visited[0][0] = true;
14
15 int dr[] = {-1, 1, 0, 0};
16 int dc[] = {0, 0, -1, 1};
17
18 while (!q.empty()) {
19 auto [r, c] = q.front();
20 q.pop();
21
22 if (r == n - 1 && c == n - 1) return true;
23
24 for (int d = 0; d < 4; ++d) {
25 int nr = r + dr[d], nc = c + dc[d];
26 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] <= t) {
27 visited[nr][nc] = true;
28 q.push({nr, nc});
29 }
30 }
31 }
32 return false;
33}
34
35int swimInWaterBinarySearch(std::vector<std::vector<int>>& grid) {
36 int n = grid.size();
37 int low = std::max(grid[0][0], grid[n - 1][n - 1]);
38 int high = n * n - 1;
39 int ans = high;
40
41 while (low <= high) {
42 int mid = low + (high - low) / 2;
43 if (canSwim(mid, grid)) {
44 ans = mid;
45 high = mid - 1;
46 } else {
47 low = mid + 1;
48 }
49 }
50 return ans;
51}
52
53int main() {
54 std::vector<std::vector<int>> grid = {{0, 2}, {1, 3}};
55 std::cout << "Swim in Water (BS): " << swimInWaterBinarySearch(grid) << std::endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(N^2 log(N^2)) = O(N^2 log N) because each BFS takes O(N^2) and binary search runs log(N^2) times.
  • Space complexity: O(N^2) for the BFS queue and visited matrix.

3. Modified Dijkstra's Algorithm (Minimax Heap)

Intuition

Using a min-heap initialized with (time = grid[0][0], r = 0, c = 0), greedily explore adjacent cells. When transitioning to neighbor (nr, nc), the required time is max(time, grid[nr][nc]). By always expanding the cell with the smallest required water level, the first time (n-1, n-1) is popped from the priority queue, the minimum time is guaranteed.

Algorithm

  1. Initialize visited matrix of size n × n with false.
  2. Initialize min-heap pq, push (grid[0][0], 0, 0).
  3. Mark visited[0][0] = true.
  4. While pq is not empty:
  5. Pop (t, r, c).
  6. If r == n - 1 && c == n - 1, return t.
  7. For each 4-directional neighbor (nr, nc):
  8. If in bounds and !visited[nr][nc]:
  9. visited[nr][nc] = true
  10. Push (max(t, grid[nr][nc]), nr, nc) into pq.
  11. Return -1 (fallback).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <tuple>
5#include <algorithm>
6
7int swimInWater(std::vector<std::vector<int>>& grid) {
8 int n = grid.size();
9 std::vector<std::vector<bool>> visited(n, std::vector<bool>(n, false));
10 // tuple: (time, r, c)
11 std::priority_queue<std::tuple<int, int, int>, std::vector<std::tuple<int, int, int>>, std::greater<>> pq;
12
13 pq.push({grid[0][0], 0, 0});
14 visited[0][0] = true;
15
16 int dr[] = {-1, 1, 0, 0};
17 int dc[] = {0, 0, -1, 1};
18
19 while (!pq.empty()) {
20 auto [t, r, c] = pq.top();
21 pq.pop();
22
23 if (r == n - 1 && c == n - 1) return t;
24
25 for (int d = 0; d < 4; ++d) {
26 int nr = r + dr[d], nc = c + dc[d];
27 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
28 visited[nr][nc] = true;
29 pq.push({std::max(t, grid[nr][nc]), nr, nc});
30 }
31 }
32 }
33 return -1;
34}
35
36int main() {
37 std::vector<std::vector<int>> grid = {{0, 2}, {1, 3}};
38 std::cout << "Optimal Swim in Water (Dijkstra): " << swimInWater(grid) << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N^2 log N) because each cell is pushed and popped from the priority queue at most once.
  • Space complexity: O(N^2) for the priority queue and visited matrix.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS BacktrackingO(4^(N^2))O(N^2)Simple recursive search.Exponential runtime; times out on grids larger than 5x5.
2.Binary Search + BFSO(N^2 log N)O(N^2)Very clean predicate function using standard BFS.Performs full BFS exploration log(N2) times.
3.Modified DijkstraOptimalO(N^2 log N)O(N^2)Greedy single-pass expansion; terminates early the instant (n-1, n-1) is popped.Requires min-heap / priority queue.

Common Pitfalls & Crucial Edge Cases

Summing elevations instead of taking the maximum.

Water level is uniform across the world; the restriction is the maximum elevation along the route, not the cumulative sum.

Initializing low to 0 in Binary Search instead of max(grid[0][0], grid[n-1][n-1]).

Starting low at 0 works but testing values below the start/end elevation wastes iterations.

Crucial Edge Cases to Validate:

  • n = 1 — Starting cell is the destination; returns grid[0][0].
  • Elevation strictly increases along the diagonal — Dijkstra effortlessly prioritizes the optimal path, returning grid[n-1][n-1].
  • Surrounded by high walls — Algorithm finds the lowest mountain pass to reach the exit.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the minimax nature of the problem clearly: 'We want to find a path from (0,0) to (n-1,n-1) that minimizes the maximum cell elevation.'
  2. Point out that both Binary Search on Answer + BFS and Modified Dijkstra achieve O(N2 log N) time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the answer be at least max(grid[0][0], grid[n-1][n-1])?

2.In Modified Dijkstra, why can a cell be marked visited immediately upon pushing to the heap?

3.What is the upper bound on the water level for an n x n grid?

Back to DSA Sheet