Course4all
Join us on telegram
Home/dsa/Union Find/Making a Large Island

Making a Large Island

Master this topic with zero to advance depth.

Making a Large Island

Change at most one 0 to 1 in a binary grid to get the largest possible island.

Hard

Examples

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

Level III: Union-Find (Component Sizes)

Intuition

Pre-calculate all island sizes using DSU. Then, for each '0', calculate the potential island size by summing sizes of all unique neighbor islands + 1.

⏱ O(N^2 \cdot \alpha(N^2))💾 O(N^2)

Detailed Dry Run

Grid: [[1,0],[0,1]]. DSU islands: {0}:sz=1, {3}:sz=1. Flip (0,1) at index 1: Neighbors indices 0 and 3 are in different islands. Total: 1+1+1 = 3.

java
import java.util.*;\nclass Solution {\n    public int largestIsland(int[][] grid) {\n        int n = grid.length; int[] p = new int[n*n], sz = new int[n*n];\n        for(int i=0; i<n*n; i++) { p[i]=i; sz[i]=1; }\n        boolean hasZero = false;\n        for(int r=0; r<n; r++) for(int c=0; c<n; c++) {\n            if(grid[r][c]==1) {\n                if(r+1<n && grid[r+1][c]==1) union(p, sz, r*n+c, (r+1)*n+c);\n                if(c+1<n && grid[r][c+1]==1) union(p, sz, r*n+c, r*n+c+1);\n            } else hasZero = true;\n        }\n        if(!hasZero) return n*n;\n        int max = 0; for(int i=0; i<n*n; i++) if(grid[i/n][i%n]==1) max = Math.max(max, sz[find(p, i)]);\n        for(int r=0; r<n; r++) for(int c=0; c<n; c++) if(grid[r][c]==0) {\n            Set<Integer> roots = new HashSet<>();\n            for(int[] d:new int[][]{{0,1},{0,-1},{1,0},{-1,0}}) {\n                int nr=r+d[0], nc=c+d[1]; if(nr>=0 && nr<n && nc>=0 && nc<n && grid[nr][nc]==1) roots.add(find(p, nr*n+nc));\n            }\n            int cur = 1; for(int root:roots) cur += sz[root];\n            max = Math.max(max, cur);\n        }\n        return max;\n    }\n    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }\n    private void union(int[] p, int[] sz, int i, int j) {\n        int r1=find(p,i), r2=find(p,j); if(r1!=r2) { p[r1]=r2; sz[r2]+=sz[r1]; }\n    }\n}
← Previous QuestionMinimize Malware Spread
Next Question →Swim in Rising Water