Swim in Rising Water
HardPrompt
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.lengthn == grid[i].length1 <= n <= 500 <= grid[i][j] < n2- Each value
grid[i][j]is unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This problem can be viewed as finding a path from the top-left to the bottom-right corner that minimizes the highest "cost" (elevation) of any cell along the path. This is a classic application for Dijkstra's algorithm or a Best-First Search. We use a priority queue to always explore the path that has the minimum-highest-elevation-so-far. The algorithm greedily expands paths with lower water level requirements, guaranteeing that when we first reach the destination, it will be via a path that requires the least possible time.
Algorithm
- Model the grid as a graph where each cell is a node.
- The problem is to find a path from
(0,0)to(n-1,n-1)that minimizes the maximum elevation on the path. This is a bottleneck shortest path problem. - Use a priority queue (min-heap) to implement a Best-First Search, which is a variant of Dijkstra's algorithm. The priority queue will store
(time, row, col)and will be ordered bytime. - Initialize a
visitedarray to keep track of visited cells. - Start by pushing the initial state
(grid[0][0], 0, 0)into the priority queue. - While the priority queue is not empty:
a. Pop the cell
(t, r, c)with the minimum timet. b. If(r, c)is the destination,tis the minimum time required. Returnt. c. For each unvisited neighbor(nr, nc)of(r, c): i. Mark the neighbor as visited. ii. The time to reach this neighbor is the maximum of the current timetand the neighbor's elevationgrid[nr][nc]. iii. Push(max(t, grid[nr][nc]), nr, nc)into the priority queue.
Walkthrough
class Solution { public int swimInWater(int[][] grid) { int n = grid.length; // Min-heap storing {max_elevation_so_far, row, col} PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); boolean[][] visited = new boolean[n][n]; pq.offer(new int[]{grid[0][0], 0, 0}); visited[0][0] = true; int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; while (!pq.isEmpty()) { int[] cell = pq.poll(); int t = cell[0]; int r = cell[1]; int c = cell[2]; if (r == n - 1 && c == n - 1) { return t; } for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) { visited[nr][nc] = true; int newTime = Math.max(t, grid[nr][nc]); pq.offer(new int[]{newTime, nr, nc}); } } } return -1; // Should not be reached given the problem constraints }}Complexity
Time
O(n^2 * log(n^2)) which simplifies to O(n^2 * log(n)). Each of the `n^2` cells is added to and removed from the priority queue at most once. Each operation on the priority queue takes O(log(n^2)) time.
Space
O(n^2) - For the `visited` array and the priority queue, which can store up to O(n^2) elements.
Trade-offs
Pros
It's a direct and elegant solution for this type of bottleneck shortest path problem.
Generally more efficient than the binary search approach as it explores the grid in a more targeted way.
Cons
Slightly more complex to understand and implement than a simple BFS if one is not familiar with Dijkstra's algorithm or priority queues.
The problem has a key monotonic property: if we can travel from the start to the end at a certain time t, we can also do so for any time t' > t. This allows us to binary search for the minimum required time t. For each guessed time t_mid, we solve a simpler decision problem: "Is it possible to reach the destination at time t_mid?". This subproblem can be solved using a standard graph traversal like BFS or DFS, where we only consider cells with elevation less than or equal to t_mid as valid.
Algorithm
- Define a search range for the answer (time
t). The minimum possible time is0and the maximum isn*n - 1. Letlow = 0,high = n*n - 1. - Perform a binary search on this range.
- For each
midvalue (a potential timet): a. Check if a path exists from(0, 0)to(n-1, n-1)using only cells(r, c)wheregrid[r][c] <= mid. b. This check can be done with a standard Breadth-First Search (BFS) or Depth-First Search (DFS). c. The BFS starts at(0, 0)and explores neighbors, but only if their elevation is at mostmid. - Based on the result of the path check:
a. If a path exists,
midis a possible answer. We try for a better (smaller) answer by settinghigh = mid - 1and storingmidas the current best answer. b. If no path exists,midis too small. We need more time, so we setlow = mid + 1. - The binary search terminates when
low > high, and the stored best answer is the minimum time required.
Walkthrough
class Solution { public int swimInWater(int[][] grid) { int n = grid.length; int low = 0, high = n * n - 1; int ans = high; while (low <= high) { int mid = low + (high - low) / 2; if (canReach(grid, mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } private boolean canReach(int[][] grid, int t) { int n = grid.length; if (grid[0][0] > t) { return false; } Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{0, 0}); boolean[][] visited = new boolean[n][n]; visited[0][0] = true; int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; while (!queue.isEmpty()) { int[] cell = queue.poll(); int r = cell[0]; int c = cell[1]; if (r == n - 1 && c == n - 1) { return true; } for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; 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
Time
O(n^2 * log(n^2)) which simplifies to O(n^2 * log(n)). The binary search performs O(log(n^2)) iterations, and each iteration involves a BFS that takes O(n^2) time in the worst case.
Space
O(n^2) - For the `visited` array and the queue used in the BFS.
Trade-offs
Pros
Conceptually simple and easy to implement.
Effectively reduces an optimization problem to a series of simpler decision problems.
Cons
It repeatedly traverses the grid, which can be less efficient than single-pass algorithms like Dijkstra's or Union-Find.
The constant factor in the time complexity might be higher compared to more direct approaches.
This approach views the problem from a connectivity perspective. We can think of the water level rising over time. As the water level t increases, more cells become 'swimmable'. We want to find the exact moment (the minimum t) when a path of swimmable cells connects the start and end points. We can simulate this process efficiently using a Union-Find (or Disjoint Set Union) data structure. We process cells in increasing order of their elevation. For each new cell that becomes swimmable, we merge its connected component with those of its already-swimmable neighbors. The answer is the elevation of the cell that causes the start and end points to be in the same component for the first time.
Algorithm
- Reframe the problem: find the earliest time
twhen(0,0)and(n-1,n-1)become connected. - Since cell elevations are a unique permutation of
0ton^2-1, we can process cells in increasing order of their elevation, which is equivalent to processing them in increasing order of timet. - Use a helper array
pos[n*n]wherepos[t]stores the coordinates(r,c)of the cell with elevationt. - Initialize a Union-Find (DSU) data structure for
n*ncells, where each cell is initially in its own set. - Iterate
tfrom0ton*n - 1: a. Get the coordinates(r, c)for the cell with elevationtfrom theposarray. b. Mark this cell as 'active' (e.g., using avisitedarray). c. For each of its 4 neighbors, if the neighbor is already active, perform aunionoperation in the DSU between the current cell and the neighbor. d. After the unions, check if(0,0)and(n-1,n-1)are in the same set using thefindoperation. e. If they are,tis the first time they become connected, so it's the minimum time required. Returnt.
Walkthrough
class Solution { class DSU { int[] parent; public DSU(int n) { parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; } public int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { parent[rootI] = rootJ; } } } public int swimInWater(int[][] grid) { int n = grid.length; DSU dsu = new DSU(n * n); boolean[][] visited = new boolean[n][n]; int[][] pos = new int[n * n][2]; // Pre-compute positions of each elevation value for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { pos[grid[i][j]][0] = i; pos[grid[i][j]][1] = j; } } int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; // Iterate through time t = 0, 1, 2, ... for (int t = 0; t < n * n; t++) { int r = pos[t][0]; int c = pos[t][1]; visited[r][c] = true; // Union with visited neighbors for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < n && nc >= 0 && nc < n && visited[nr][nc]) { dsu.union(r * n + c, nr * n + nc); } } // Check if start and end are connected if (dsu.find(0) == dsu.find(n * n - 1)) { return t; } } return -1; // Should not be reached }}Complexity
Time
O(n^2 * α(n^2)), where α is the Inverse Ackermann function. The loop runs `n^2` times, and inside, we perform a constant number of DSU operations, which have an amortized time complexity of α(n^2), a value that is nearly constant for all practical purposes. This is slightly better than O(n^2 log n).
Space
O(n^2) - For the DSU's parent array, the `visited` array, and the `pos` array to store coordinates.
Trade-offs
Pros
Asymptotically the most efficient approach due to near-constant time DSU operations.
Provides an elegant solution by modeling the problem as a dynamic connectivity problem.
Cons
The most efficient implementation relies on the specific problem constraint that elevations are a permutation of
0..n^2-1. If elevations were arbitrary, an explicit sorting stepO(n^2 log n)would be needed, making its complexity equal to Dijkstra's.The concept of Union-Find might be less familiar than standard graph traversals.
Solutions
Solution
class Solution {private int[] p;public int swimInWater(int[][] grid) { int n = grid.length; p = new int[n * n]; for (int i = 0; i < p.length; ++i) { p[i] = i; } int[] hi = new int[n * n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { hi[grid[i][j]] = i * n + j; } } int[] dirs = {-1, 0, 1, 0, -1}; for (int t = 0; t < n * n; ++t) { int i = hi[t] / n; int j = hi[t] % n; for (int k = 0; k < 4; ++k) { int x = i + dirs[k]; int y = j + dirs[k + 1]; if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] <= t) { p[find(x * n + y)] = find(i * n + j); } if (find(0) == find(n * n - 1)) { return t; } } } return -1; }private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }}class Solution {public: vector<int> p; int swimInWater(vector<vector<int>> &grid) { int n = grid.size(); p.resize(n * n); for (int i = 0; i < p.size(); ++i) p[i] = i; vector<int> hi(n * n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) hi[grid[i][j]] = i * n + j; vector<int> dirs = {-1, 0, 1, 0, -1}; for (int t = 0; t < n * n; ++t) { int i = hi[t] / n, j = hi[t] % n; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] <= t) p[find(x * n + y)] = find(hi[t]); if (find(0) == find(n * n - 1)) return t; } } return -1; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }};class Solution: def swimInWater(self, grid: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] n = len(grid) p = list(range(n * n)) hi = [0] * (n * n) for i, row in enumerate(grid): for j, h in enumerate(row): hi[h] = i * n + j for t in range(n * n): i, j = hi[t] // n, hi[t] % n for a, b in [(0, - 1), (0, 1), (1, 0), (- 1, 0)]: x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y] <= t: p[find(x * n + y)] = find(hi[t]) if find(0) == find(n * n - 1): return t return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.