The distinct roots of its adjacent land components and their stored sizes. Add those sizes plus one for the newly created land square.

Flatten (r,c) into r*columns+c. Join neighboring land cells once. Union-find preserves component size at each root. For a candidate flip, at most four neighboring roots can contribute; a set prevents duplicate contributions from one wrapping island. Existing islands also remain candidates, which handles an all-land grid. Flood-fill component labels are an equally valid static preprocessing method; DSU is useful here to reuse the merge-and-summary model.

What the function promises: For a nonempty square binary grid, return the largest four-neighbor land component after changing at most one zero to one. The helper also handles rectangular and empty grids and does not mutate them.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

def largest_island(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    groups = DisjointSet(rows * cols)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                for nr, nc in ((r-1, c), (r, c-1)):
                    if nr >= 0 and nc >= 0 and grid[nr][nc] == 1:
                        groups.union(r*cols+c, nr*cols+nc)
    best = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                best = max(best, groups.size[groups.find(r*cols+c)])
                continue
            roots = set()
            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    roots.add(groups.find(nr*cols+nc))
            best = max(best, 1 + sum(groups.size[root] for root in roots))
    return best

assert largest_island([[1, 1], [1, 0]]) == 4
assert largest_island([[1, 0], [0, 1]]) == 3
assert largest_island([[0, 0], [0, 0]]) == 1
assert largest_island([[1, 1], [1, 1]]) == 4

Work and storage: O(RC α(RC)) time and O(RC) space. Each cell has only four possible neighbors; the deduplication set is constant-sized.

When to recognize it: One flip joins neighboring groups. Their roots and sizes summarize everything needed to score that flip.

Check before applying it: Two neighboring squares may belong to the same island. Count each root once. Trying two flips independently would miss their interaction.

No. Scores may overlap, and two adjacent flips can connect components neither would connect alone. The one-local-change summary does not establish independence between two changes.