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

Swim in Rising Water

Master this topic with zero to advance depth.

Swim in Rising Water

Find the minimum time t needed to reach the bottom-right from the top-left in a grid with elevations.

Hard

Examples

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

Level III: Union-Find (Threshold Connectivity)

Intuition

Sort all cells by elevation. Add cells to DSU one by one in increasing order of tt (elevation). Stop when top-left and bottom-right are in the same component.

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

Detailed Dry Run

Cells sorted by elevation: (0,0):0, (1,0):1, (0,1):2, (1,1):3. At t=3, (1,1) is added, connecting everything. Result=3.

java
import java.util.*;\nclass Solution {\n    public int swimInWater(int[][] grid) {\n        int n = grid.length; int[] pos = new int[n*n];\n        for(int r=0; r<n; r++) for(int c=0; c<n; c++) pos[grid[r][c]] = r*n+c;\n        int[] p = new int[n*n]; for(int i=0; i<n*n; i++) p[i]=i;\n        boolean[] open = new boolean[n*n];\n        for(int t=0; t<n*n; t++) {\n            int r=pos[t]/n, c=pos[t]%n; open[pos[t]]=true;\n            for(int[] d:new int[][]{{0,1},{0,-1},{1,0},{-1,0}}) {\n                int nr=r+d[0], nc=c+d[1];\n                if(nr>=0 && nr<n && nc>=0 && nc<n && open[nr*n+nc]) p[find(p, pos[t])] = find(p, nr*n+nc);\n            }\n            if(open[0] && open[n*n-1] && find(p, 0) == find(p, n*n-1)) return t;\n        }\n        return -1;\n    }\n    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }\n}
← Previous QuestionMaking a Large Island
Next Question →Single Number