Problem Summary

You are given an n x n binary grid where:

• 1 represents land
• 0 represents water

You may change at most one 0 to 1.

Your task is to return the size of the largest island you can achieve after performing at most one such change.

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

Example
Input:

[[1, 0],
 [0, 1]]

Output: 3

Explanation:
Turning either zero into one forms an island of size three.

Another Example
Input:

[[1,1],
 [1,1]]

Output: 4

Explanation: Grid is already full of land. No need to flip anything.

Constraints

• 1 ≤ n ≤ 500
• Must run efficiently (cannot afford BFS/DFS on every flip)

---

Approach (Simple English)

The challenge is to determine which zero to flip so that the resulting island is as large as possible.
A naive approach would try flipping each zero and computing island sizes each time, but this is too slow: O(n²) flips * O(n²) DFS = O(n⁴).

Instead, we solve it in two efficient phases.

---

Phase 1: Label All Existing Islands

We first find all the islands already present in the grid.

Key Idea

Assign a unique ID to each separate island and compute its size.

For example:

1 1 0 1
1 0 0 1

might become:

2 2 0 3
2 0 0 3

Where:

• Island with ID 2 has size 3
• Island with ID 3 has size 2

Why This Works

If we know each island’s ID and size, then flipping a zero to one allows us to connect multiple islands instantly.

We store island sizes in a map:

id -> size

---

Phase 2: Try Flipping Each Zero Smartly

For every 0 cell, we check its up to four neighbors.

If those neighbors belong to different island IDs, flipping this zero connects all those islands.

Key Idea

For cell (i, j):

• Check neighbors
• Collect their unique island IDs
• Compute:
  newSize = 1 (the flipped cell) + sum of sizes of all distinct neighboring islands

Take the maximum across all zeros.

Why This Works

Each zero can potentially act as a “bridge” connecting islands around it.
Since we already precomputed island sizes, evaluating each zero is O(1).

---

Special Case

If the grid has no zeros, the answer is simply the size of the entire grid.

---

Java Code (Efficient O(n²) Solution)

import java.util.*;

class Solution {

    private int n;
    private int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    public int largestIsland(int[][] grid) {
        n = grid.length;

        int id = 2;  // start labeling islands from value 2
        Map<Integer, Integer> sizeMap = new HashMap<>();

        // Step 1: Label all islands and record sizes
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int size = dfs(grid, i, j, id);
                    sizeMap.put(id, size);
                    id++;
                }
            }
        }

        int maxSize = 0;

        // If no zeros, entire grid is land
        if (sizeMap.isEmpty()) {
            return n * n;
        }

        // Track existing island sizes too
        for (int s : sizeMap.values()) {
            maxSize = Math.max(maxSize, s);
        }

        // Step 2: Try flipping each zero
        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 newSize = 1;  // this zero becomes land

                    for (int[] d : dirs) {
                        int r = i + d[0];
                        int c = j + d[1];

                        if (r >= 0 && r < n && c >= 0 && c < n) {
                            int neighborId = grid[r];
                            if (neighborId > 1 && !seen.contains(neighborId)) {
                                seen.add(neighborId);
                                newSize += sizeMap.get(neighborId);
                            }
                        }
                    }
                    maxSize = Math.max(maxSize, newSize);
                }
            }
        }

        return maxSize;
    }

    private int dfs(int[][] grid, int i, int j, int id) {
        if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1) {
            return 0;
        }

        grid[i][j] = id;
        int size = 1;

        for (int[] d : dirs) {
            size += dfs(grid, i + d[0], j + d[1], id);
        }
        return size;
    }
}

---

Dry Run

Grid:

1 0
0 1

Phase 1: Label islands

Start id = 2.

• Cell (0,0) = 1 → label with 2 → island size = 1
• Cell (1,1) = 1 → label with 3 → island size = 1

Grid becomes:

2 0
0 3

sizeMap:
2 -> 1
3 -> 1

maxSize initially = 1

Phase 2: Try flipping zeros

Check (0,1):

• Neighbor up: invalid
• Neighbor down: 3
• Neighbor left: 2
  Unique islands = {2, 3}
  newSize = 1 + 1 + 1 = 3 → maxSize = 3

Check (1,0):

• Neighbors similarly connect islands 2 and 3
  newSize = 3

Final answer = 3

---

Complexity Analysis

Time Complexity:
O(n²)

• One DFS per island
• Checking each zero in O(1) with hash sets
• Overall efficient for n ≤ 500

Space Complexity:
O(n²)

• DFS recursion, map storage, modified grid

---

Edge Cases

• All land → return n²
• All water → flipping one zero creates island of size 1
• Islands already large, flipping may or may not help
• Large n (500) requires efficient O(n²) solution