Making a Large Island

Given a binary grid, change at most one 0 to 1 to maximize the size of the largest island. Return the maximum island size.

Example 1

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

Example 2

Input: [[1,1],[1,0]] → Output: 4

Solution Approach

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

Java

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)