Course4all
Join us on telegram
Home/dsa/Graphs/Swim in Rising Water

Swim in Rising Water

Master this topic with zero to advance depth.

Swim in Rising Water

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

At time t, the water level everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares are at most t. You can swim infinite distances in zero time. You start at the top left square (0, 0) at time 0.

Return the least time until you can reach the bottom right square (n - 1, n - 1).

Visual Representation

Grid: 0 1 2 3 4 5 6 7 8 You start at 0. You need time 8 to reach 8 because the bottom-right corner itself is 8. At t=8, all cells are <= 8, so a path exists. Result: 8
Hard

Examples

Input: grid = [[0,2],[1,3]]
Output: 3

At time 3, we can swim along the path 0-1-3.

Approach 1

Level II: Intermediate (Binary Search on Answer + BFS)

Intuition

Since the possible time answers range from 0 to N2−1N^2-1, we can binary search for the minimum time TT such that there is a path from (0,0)(0,0) to (N−1,N−1)(N-1,N-1) using only cells with elevation \≤T\≤ T.

Thought Process

  1. Search range low = 0, high = N*N - 1.
  2. For each mid (candidate time):
    • Run a BFS/DFS from (0,0).
    • Only move to neighbors with grid[nr][nc] <= mid.
    • If (N-1, N-1) is reachable, mid is possible; try lower.
    • Otherwise, mid is impossible; try higher.

Why it's Level II

It's very robust and often easier to come up with than the Dijkstra/heap-based approach.

⏱ O(N^2 log(N^2)) = O(N^2 log N).💾 O(N^2) - For BFS visited array.

Detailed Dry Run

3x3, grid[0][0]=3, grid[2][2]=5

  1. high=8, low=0. mid=4. Can we reach 2,2? Start (0,0) is 3. OK. BFS explores neighbors <= 4. If path exists, high=4.
  2. mid=2. grid[0][0]=3 > 2. Impossible. low=3.
  3. Continue binary search.
java
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int l = 0, r = n * n - 1, res = r;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (canReach(mid, grid)) {
                res = mid; r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
    private boolean canReach(int t, int[][] grid) {
        int n = grid.length;
        if (grid[0][0] > t) return false;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        boolean[][] vis = new boolean[n][n];
        vis[0][0] = true;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            if (curr[0] == n - 1 && curr[1] == n - 1) return true;
            for (int[] d : dirs) {
                int nr = curr[0] + d[0], nc = curr[1] + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !vis[nr][nc] && grid[nr][nc] <= t) {
                    vis[nr][nc] = true; q.add(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
}
Approach 2

Level III: Optimal (Dijkstra's Algorithm)

Intuition

This is a pathfinding problem where the weight of a path is the maximum elevation on that path. We want to find the path with the minimum such weight. This is a variant of Dijkstra where the 'distance' is the max-so-far elevation.

Thought Process

  1. Use a Min-Heap/Priority Queue to store (max_elevation_so_far, r, c).
  2. Start with (grid[0][0], 0, 0).
  3. Keep a visited set to avoid cycles.
  4. In each step:
    • Pop (t, r, c). This t is the minimum time needed to reach this cell.
    • If (r, c) is (n-1, n-1), return t.
    • For each 4-directional neighbor (nr, nc):
      • The time needed to reach neighbor is max(t, grid[nr][nc]).
      • If unvisited, push to queue.

Pattern: Min-Max Path (Dijkstra)

⏱ O(N^2 log N) - Standard Dijkstra on N^2 nodes.💾 O(N^2) - For minDist array and PQ.

Detailed Dry Run

Grid: [[0,2],[1,3]]

  1. PQ: [(0, 0, 0)]
  2. Pop (0,0,0). Neighbors: (0,1): max(0,2)=2, (1,0): max(0,1)=1.
  3. PQ: [(1, 1, 0), (2, 0, 1)]
  4. Pop (1,1,0). Neighbors: (1,1): max(1,3)=3.
  5. PQ: [(2, 0, 1), (3, 1, 1)]
  6. Pop (2,0,1). Neighbors: (1,1): max(2,3)=3. (Already in PQ with 3, no update).
  7. Pop (3,1,1). Reached (1,1). Return 3. Result: 3
java
import java.util.*;

public class Main {
    public static int swimInWater(int[][] grid) {
        int n = grid.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{grid[0][0], 0, 0});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;

        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int t = curr[0], r = curr[1], c = curr[2];
            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]) {
                    visited[nr][nc] = true;
                    pq.offer(new int[]{Math.max(t, grid[nr][nc]), nr, nc});
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // Test setup
    }
}
← Previous QuestionMinimum Cost to Connect All Points
Next Question →Critical Connections in a Network