MANG Problem #41: Making A Large Island (Hard)

1. Problem Statement

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

2. Approach: Connected Components (DFS)

A brute-force approach would change each 0 to 1 and run a full DFS/BFS ($O(N^4)$). We must optimize this.

The "Aha!" Moment

Instead of flipping 0s and checking sizes, we should first measure the existing islands and give them "IDs".

1. First Pass (Coloring): Traverse the grid. When a 1 is found, run a DFS to find the area of the island. Give every cell in this island a unique id (e.g., 2, 3, 4...) and store Map<id, area>.
2. Second Pass (Flipping): Traverse the grid looking for 0s.
   • If you flip a 0 to 1, it connects all adjacent islands.
   • Check the 4 neighbors. Collect their unique ids in a HashSet (to avoid double-counting the same island).
   • The new area is 1 + sum(Map.get(id) for each unique id).
   • Update maxArea.

3. Java Implementation

public int largestIsland(int[][] grid) {
    int n = grid.length;
    Map<Integer, Integer> areaMap = new HashMap<>();
    int islandId = 2; // Start IDs at 2 because 0 and 1 are already used
    int maxArea = 0;
    
    // 1. Paint islands and store areas
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                int area = dfs(grid, i, j, islandId);
                areaMap.put(islandId, area);
                maxArea = Math.max(maxArea, area); // In case there are no 0s
                islandId++;
            }
        }
    }
    
    // 2. Try flipping every 0
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                Set<Integer> neighborIds = new HashSet<>();
                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] >= 2) {
                        neighborIds.add(grid[ni][nj]);
                    }
                }
                
                int potentialArea = 1; // The flipped 0
                for (int id : neighborIds) {
                    potentialArea += areaMap.get(id);
                }
                maxArea = Math.max(maxArea, potentialArea);
            }
        }
    }
    
    return maxArea == 0 ? 1 : maxArea; // Handle all 0s case
}

private int dfs(int[][] grid, int r, int c, int id) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != 1) return 0;
    grid[r][c] = id;
    return 1 + dfs(grid, r+1, c, id) + dfs(grid, r-1, c, id) + 
               dfs(grid, r, c+1, id) + dfs(grid, r, c-1, id);
}

4. 5-Minute "Video-Style" Walkthrough

1. The Component Identification: By changing the 1s to an ID like 2 or 3, the grid itself becomes a map of components. We don't need an extra 2D array.
2. The HashSet: Why use a Set for neighbor IDs? Because a 0 might be surrounded by 1s that all belong to the same island. If we don't deduplicate the IDs, we would add the area of the same island multiple times!

5. Interview Discussion

• Interviewer: "What is the time complexity?"
• You: "O(N^2). The first pass visits each cell at most a constant number of times (DFS). The second pass visits each cell and checks 4 neighbors. It is strictly linear relative to the grid size."
• Interviewer: "Can this be solved with Union Find (Disjoint Set)?"
• You: "Yes. We can treat all 1s as nodes and union adjacent 1s to form components, tracking sizes. The logic for the second pass remains exactly the same."