Given a binary grid, change at most one 0 to 1 to maximize the size of the largest island. Return the maximum island size.
Input: [[1,0],[0,1]] → Output: 3Input: [[1,1],[1,0]] → Output: 4
Label each island with a unique ID and record its size. For each 0-cell, check the 4 neighboring island IDs and sum their sizes + 1.
- DFS to label each island (1,2,3,...) and record sizes in a map.
- For each 0-cell: collect distinct neighboring island IDs, sum sizes + 1.
- Answer = max of all such sums, also considering if grid is all 1s (return n*n).
import java.util.*;
class Solution {
int m, n;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public int largestIsland(int[][] grid) {
m = grid.length; n = grid[0].length;
Map<Integer,Integer> islandSize = new HashMap<>();
int id = 2;
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
if (grid[i][j] == 1) { int sz = dfs(grid,i,j,id); islandSize.put(id++,sz); }
int max = islandSize.values().stream().mapToInt(Integer::intValue).max().orElse(0);
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
Set<Integer> seen = new HashSet<>();
int sz = 1;
for (int[] d : dirs) {
int r=i+d[0], c=j+d[1];
if (r>=0&&r<m&&c>=0&&c<n&&grid[r][c]>1&&seen.add(grid[r][c]))
sz += islandSize.get(grid[r][c]);
}
max = Math.max(max, sz);
}
}
return max;
}
private int dfs(int[][] g, int r, int c, int id) {
if (r<0||r>=m||c<0||c>=n||g[r][c]!=1) return 0;
g[r][c]=id;
return 1+dfs(g,r+1,c,id)+dfs(g,r-1,c,id)+dfs(g,r,c+1,id)+dfs(g,r,c-1,id);
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)