Making A Large Island

Share

Flip at most one 0 to 1. Find maximum island size possible.

Example 1
Input: grid=[[1,0],[0,1]] → Output: 3
Example 2
Input: grid=[[1,1],[1,0]] → Output: 4

Solution Approach

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)
Java
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)