Flip at most one 0 to 1. Find maximum island size possible.
Input: grid=[[1,0],[0,1]] → Output: 3
Input: grid=[[1,1],[1,0]] → Output: 4
DFS to label each island with an id and size. For each 0 cell, sum adjacent unique island sizes + 1.
- DFS to label islands (id=2,3,4...) and compute size[]
- For each 0 cell: collect adjacent island ids
- Answer = 1 + sum of unique adjacent island sizes
- Also consider no flip needed (max island as-is)
public int largestIsland(int[][] grid) {
int n = grid.length, id = 2;
int[] size = new int[n * n + 2];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) { size[id] = dfs(grid, i, j, id); id++; }
int max = Arrays.stream(size).max().getAsInt();
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (grid[i][j] == 0) {
Set<Integer> seen = new HashSet<>();
int total = 1;
for (int[] d : dirs) {
int ni=i+d[0], nj=j+d[1];
if (ni>=0&&ni<n&&nj>=0&&nj<n&&grid[ni][nj]>1&&seen.add(grid[ni][nj]))
total += size[grid[ni][nj]];
}
max = Math.max(max, total);
}
return max;
}
private int dfs(int[][] g, int i, int j, int id) {
if (i<0||i>=g.length||j<0||j>=g[0].length||g[i][j]!=1) return 0;
g[i][j]=id;
return 1+dfs(g,i+1,j,id)+dfs(g,i-1,j,id)+dfs(g,i,j+1,id)+dfs(g,i,j-1,id);
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)