Course4all

Swim in Rising Water

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionKth Smallest Element in a Sorted Matrix
Next Question →Minimum Number of Days to Make m Bouquets