Making a Large Island — DFS Color Map + Merge

Problem

You may change at most one 0 to 1. Return the size of the largest island.

Approach — Two-Pass DFS

Pass 1: DFS each island, label it with a unique color (≥2), record size[color]. Pass 2: For each 0 cell, sum sizes of distinct neighboring islands + 1. Track max.

Time: O(mn) | Space: O(mn)

Solutions

Python

class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        R,C=len(grid),len(grid[0])
        color=2; sizes={}
        def dfs(r,c,col):
            if not(0<=r<R and 0<=c<C) or grid[r][c]!=1: return 0
            grid[r][c]=col
            return 1+dfs(r+1,c,col)+dfs(r-1,c,col)+dfs(r,c+1,col)+dfs(r,c-1,col)
        for r in range(R):
            for c in range(C):
                if grid[r][c]==1:
                    sizes[color]=dfs(r,c,color); color+=1
        ans=max(sizes.values()) if sizes else 0
        for r in range(R):
            for c in range(C):
                if grid[r][c]==0:
                    seen=set()
                    total=1
                    for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                        nr,nc=r+dr,c+dc
                        if 0<=nr<R and 0<=nc<C and grid[nr][nc]>1:
                            col=grid[nr][nc]
                            if col not in seen:
                                seen.add(col); total+=sizes[col]
                    ans=max(ans,total)
        return ans

Complexity

Time: O(mn) | Space: O(mn)