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

Swim in Rising Water

Master this topic with zero to advance depth.

Swim in Rising Water

On an N×NN \times N grid, elevation at (i, j) is grid[i][j]. Return the least time TT such that you can swim from top-left to bottom-right.

Hard

Examples

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

Level I: Dijkstra (Min-Max Path)

Intuition

This is a variant of shortest path where the 'cost' of a path is max(\\max(elevations on path)). Dijkstra's algorithm with a min-priority queue works perfectly.

⏱ $O(N^2 \\log N)$💾 $O(N^2)$

Detailed Dry Run

grid = [[0,2],[1,3]].

  • Start (0,0) elev 0.
  • Neighbors: (0,1) cost 2, (1,0) cost 1.
  • Smallest max: (1,0) cost 1.
  • Neighbor of (1,0) is (1,1) cost 3.
  • Result: 3.
java
class Solution {
    public 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[][] vis = new boolean[n][n];
        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (vis[cur[1]][cur[2]]) continue; vis[cur[1]][cur[2]] = true;
            if (cur[1] == n - 1 && cur[2] == n - 1) return cur[0];
            for (int[] d : dirs) {
                int ni = cur[1] + d[0], nj = cur[2] + d[1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n && !vis[ni][nj])
                    pq.offer(new int[]{Math.max(cur[0], grid[ni][nj]), ni, nj});
            }
        }
        return -1;
    }
}
Approach 2

Level II: Optimal (Union Find / Kruskal's)

Intuition

Treat the grid as a graph where each edge has a weight equal to the maximum elevation of its two endpoints. Sort all possible edge weights (or cell elevations). Add cells one by one in increasing order of elevation and connect them with their visited neighbors. The first time the top-left and bottom-right are in the same component, the current elevation is the answer.

⏱ $O(N^2 \\log N^2)$💾 $O(N^2)$

Detailed Dry Run

grid = [[0,2],[1,3]].

  1. Cells sorted by elevation: (0,0):0, (1,0):1, (0,1):2, (1,1):3.
  2. Add (0,0). Add (1,0), connect to (0,0).
  3. Add (0,1), connect to (0,0).
  4. Add (1,1), connect to (1,0) and (0,1).
  5. (0,0) and (1,1) are connected. Result: 3.
java
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] positions = new int[n * n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) positions[grid[i][j]] = new int[]{i, j};
        }
        UnionFind uf = new UnionFind(n * n);
        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for (int t = 0; t < n * n; t++) {
            int r = positions[t][0], c = positions[t][1];
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] <= t) {
                    uf.union(r * n + c, nr * n + nc);
                }
            }
            if (uf.connected(0, n * n - 1)) return t;
        }
        return -1;
    }
    class UnionFind {
        int[] parent;
        UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        void union(int i, int j) {
            int rootI = find(i), rootJ = find(j);
            if (rootI != rootJ) parent[rootI] = rootJ;
        }
        boolean connected(int i, int j) { return find(i) == find(j); }
    }
}
Approach 3

Level III: Optimal (Binary Search + DFS/BFS)

Intuition

The answer TT lies in [0,N2−1][0, N^2-1]. For a fixed TT, we check if a path exists using only squares with elevation leT\\le T using BFS/DFS.

⏱ $O(N^2 \\cdot \\log(N^2))$💾 $O(N^2)$

Detailed Dry Run

grid = [[0,2],[1,3]]. BS on range [0, 3]. Try T=2: Path (0,0)->(1,0) works, but (1,0) neighbors are (1,1) elev 3 > 2. Fails. Try T=3: Path (0,0)->(1,0)->(1,1) works! Possible. Result: 3.

java
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length, l = grid[0][0], r = n * n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (canReach(grid, mid)) r = mid; else l = mid + 1;
        }
        return l;
    }
    boolean canReach(int[][] g, int t) {
        int n = g.length;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0});
        boolean[][] vis = new boolean[n][n]; vis[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == n-1 && cur[1] == n-1) return true;
            for (int[] d : new int[][]{{0,1},{0,-1},{1,0},{-1,0}}) {
                int ni = cur[0]+d[0], nj = cur[1]+d[1];
                if (ni>=0 && ni<n && nj>=0 && nj<n && !vis[ni][nj] && g[ni][nj] <= t) {
                    vis[ni][nj] = true; q.offer(new int[]{ni, nj});
                }
            }
        }
        return false;
    }
}
← Previous QuestionKth Smallest Element in a Sorted Matrix
Next Question →Minimum Number of Days to Make m Bouquets