In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).
Example 1:
Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:
Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
 
Notes:

1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.

Difficulty: interview

Starter code:

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for i in range(len(grid)):
            grid[i].insert(0, 0)
            grid[i].append(0)
        grid.insert(0, [0 for i in range(len(grid[0]))])
        grid.append([0 for i in range(len(grid[0]))])
        islands = []
        max_length = 1
        for i in range(1, len(grid) - 1):
            for j in range(1, len(grid[0]) - 1):
                if grid[i][j] != 1:
                    continue
                island_id = len(islands)
                length = 0
                connect_length = 0
                queue = [(i, j)]
                grid[i][j] = 2 + island_id
                while queue:
                    x, y = queue.pop()
                    for dx, dy in directions:
                        this_grid = grid[x + dx][y + dy]
                        if this_grid == 1:
                            grid[x + dx][y + dy] = 2 + island_id
                            queue.append((x + dx, y + dy))
                        elif isinstance(this_grid, list):
                            new_connect = 0
                            already = False
                            for old_island_id in this_grid:
                                if old_island_id != island_id:
                                    new_connect += islands[old_island_id]
                                else:
                                    already = True
                            if not already:
                                connect_length = max(connect_length, new_connect)
                                this_grid.append(island_id)
                        else:
                            grid[x + dx][y + dy] = [island_id]
                    length += 1
                islands.append(length)
                max_length = max(max_length, length + connect_length + 1)
        return min(max_length, (len(grid) - 2) * (len(grid[0]) - 2))

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        n_rows = len(grid)
        n_cols = len(grid[0])
        
        borders = dict()
        seen = set()
        max_size = 0
        
        def bfs(r, c):
            nonlocal max_size
            size = 1
            border = set()
            stack = [(r, c)]
            while stack:
                r, c = stack.pop()
                for r, c in [(r+1, c), (r-1, c), (r, c-1), (r, c+1)]:
                    if 0 <= r < n_rows and 0 <= c < n_cols and (r,c) not in seen:
                        
                        if grid[r][c] == 1:
                            size += 1
                            stack.append((r, c))
                            seen.add((r, c))
                        else:
                            border.add((r, c))
            
            max_size = max(max_size, size)
            for r, c in border:
                if (r, c) in borders:
                    max_size = max(max_size, borders[(r, c)] + size)
                    borders[(r, c)] = borders[(r, c)] + size
                else:
                    borders[(r, c)] = size
            
            
        for r in range(n_rows):
            for c in range(n_cols):
                if grid[r][c] == 1 and (r, c) not in seen:
                    seen.add((r, c))
                    bfs(r, c)
                    
        return max_size + 1 if max_size != n_rows*n_cols else max_size

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        nei = [(0,1),(1,0),(0,-1),(-1,0)]
        m, n = len(grid), len(grid[0])
        rec = dict()
        ans = 0
        def count(grid, i, j):
            cnt = 1
            grid[i][j] = -1
            for dx, dy in nei:
                nx, ny = i + dx, j + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                    cnt += count(grid, nx, ny)
                    
            return cnt
        
        def flip(grid, i, j, val):
            grid[i][j] = val
            
            for dx, dy in nei:
                nx, ny = i + dx, j + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == -1:
                    flip(grid, nx, ny, val)
                    
            return
        
        color = 2
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    temp = count(grid, i, j)
                    flip(grid, i, j, color)
                    rec[color] = temp
                    color += 1
                    ans = max(ans, temp)
        
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    visit = set()
                    for dx, dy in nei:
                        nx, ny = i + dx, j + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != 0:
                            visit.add(grid[nx][ny])
                            
                    ans = max(ans, 1 + sum(rec[i] for i in visit))
           
        return ans
                    
        
        
        


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        islandId = 2
        areaDict = {}
        maxArea = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    areaDict[islandId] = self.dfs(grid, i, j, m, n, islandId)
                    maxArea = max(maxArea, areaDict[islandId])
                    islandId += 1
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    neighborIslands = set()
                    for ni, nj in self.getNeighbors(grid, i, j, m, n):
                        if grid[ni][nj] > 0:
                            neighborIslands.add(grid[ni][nj])
                            
                    maxArea = max(maxArea, 1 + sum([areaDict[islandId] for islandId in neighborIslands]))
        
        return maxArea

    def dfs(self, grid, i, j, m, n, islandId):
        area = 1
        grid[i][j] = islandId
        for ni, nj in self.getNeighbors(grid, i, j, m, n):
            if grid[ni][nj] != 1:
                continue
            area += self.dfs(grid, ni, nj, m, n, islandId)
        return area
    
    def bfs(self, grid, i, j, m, n, islandId):
        grid[i][j] = islandId
        area = 1
        q = [(i, j)]
        while q:
            x, y = q.pop(0)
            for nx, ny in self.getNeighbors(grid, x, y, m, n):
                if grid[nx][ny] != 1:
                    continue
                area += 1
                grid[nx][ny] = islandId
                q.append((nx, ny))
        
        return area
    
    def getNeighbors(self, grid, x, y, m, n):
        result = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
        return [
            (a, b)
            for a, b in result
            if 0 <= a < m and 0 <= b < n and grid[a][b] > 0
        ]

\"\"\"
dfs timeO(mn) spaceO(mn)
1. get area of an island (similar to LC200, 695)
2. set visited nodes to 2,3,4, ... for 1st, 2nd,3rd ... islands
3. store the maxArea of islands
4. for each 0, check its 4 neighbors.if a neighbor is not 0, get its area. try to fill this 0 and connect its neighbor islands
\"\"\"

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return 0
        self.grid = grid
        mark = 1
        mark2island = {}
        mark2island[0]=0
        maxArea = 0
        
        # get area of each island; mark them as 2,3,... timeO(mn)
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if self.grid[i][j] == 1: # found a new island
                    mark+=1
                    area = self.getArea(i,j,mark)
                    mark2island[mark] = area
                    maxArea = max(maxArea,area)
        
        # check each 0, try connect it to 4 neighbors timeO(mn)
        maxNewIsland = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if self.grid[i][j] == 0: # found a new 0
                    tempArea = 1 # the grid itself
                    neighborIslands = set() # must use set to avoid duplicates
                    for d in ([0,1],[0,-1],[1,0],[-1,0]):
                        neighborIslands.add(self.getMark(i+d[0], j+d[1]))
                    for m in neighborIslands:
                        tempArea+=mark2island[m]
                    # print(i,j,tempArea)
                    maxNewIsland = max(maxNewIsland,tempArea)
        # print(self.grid)
        return max(maxNewIsland,maxArea) # the max can be an existing island
        
                    
        
    def getArea(self,i,j,mark):
        if 0<=i<len(self.grid) and 0<=j<len(self.grid[0]) and self.grid[i][j]==1: 
            self.grid[i][j] = mark # set visited node to 'mark' (e.g. 2,3,4)
            return 1+self.getArea(i+1,j,mark)+self.getArea(i-1,j,mark)+self.getArea(i,j+1,mark)+self.getArea(i,j-1,mark)
        return 0
    
    def getMark(self,i,j): # get a grid's mark
        if 0<=i<len(self.grid) and 0<=j<len(self.grid[0]):
            return self.grid[i][j]
        return 0
        
        

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        def neighbors(r, c):
            for nr, nc in [(r+1, c), (r, c+1), (r-1, c), (r, c-1)]:
                if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
                    yield nr, nc
        
        def dfs(r, c, island_num):
            island_area = 1
            grid[r][c] = island_num
            for nr, nc in neighbors(r, c):
                if grid[nr][nc] == 1:
                    island_area += dfs(nr, nc, island_num)
            return island_area
        
        area = {}
        island_num = 2
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    area[island_num] = dfs(r, c, island_num)
                    island_num += 1
        
        ans = max(area.values() or [0])
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 0:
                    neighboring_islands = set()
                    for nr, nc in neighbors(r, c):
                        if grid[nr][nc] > 1:
                            neighboring_islands.add(grid[nr][nc])
                            
                    ans = max(ans, 1+sum(area[i] for i in neighboring_islands))
        return ans

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        m, n = len(grid), len(grid[0])
    
        def move(i, j):
            for (x, y) in ((1,0),(-1,0),(0,1),(0,-1)):
                if 0<=i+x<m and 0<=j+y<n:
                    yield i+x, j+y

        def dfs(i, j, key):
            res = 0
            grid[i][j] = key
            for x, y in move(i, j):
                if grid[x][y] == 1:
                    res += dfs(x, y, key)
            return res + 1

        ## map each island to distinct keys
        mappings = {0:0}
        index = 2
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    mappings[index] = dfs(i, j, index)
                    index += 1

        res = max(mappings.values()) 
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    temp = set(grid[x][y] for x,y in move(i, j))
                    res = max(res, sum(mappings[key] for key in temp)+1)

        return res           


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        u = {(r, c): (r, c) for r, row in enumerate(grid) for c, v in enumerate(row) if v}

        def head(p):
            if u[p] == p:
                return p
            u[p] = head(u[p])
            return u[p]

        for r, row in enumerate(grid):
            for c, v in enumerate(row):
                if not v:
                    continue

                for nr, nc in [(r - 1, c), (r, c - 1)]:
                    if nr < 0 or nc < 0 or not grid[nr][nc]:
                        continue

                    u[head((r, c))] = head((nr, nc))

        islands = {p: 0 for p, h in list(u.items()) if p == h}
        for p in u:
            islands[head(p)] += 1

        max_size = max(list(islands.values()), default=0)
        for r, row in enumerate(grid):
            for c, v in enumerate(row):
                if v:
                    continue

                connected = set()
                for nr, nc in [(r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)]:
                    if nr < 0 or nc < 0 or nr >= len(grid) or nc >= len(row) or not grid[nr][nc]:
                        continue

                    if (nr, nc) in u:
                        connected.add(head((nr, nc)))

                size = 1 + sum(islands[i] for i in connected)
                max_size = max(max_size, size)

        return max_size



class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        nrows,ncols=len(grid),len(grid[0])
        dp=[ [ (0,0) for _ in range(ncols)] for _ in range(nrows) ]
        
        cum_visited=set()
        isl_no=1
        maxsize=0
        for r in range(nrows):
            for c in range(ncols):
                if (r,c) not in cum_visited and grid[r][c]==1:
                    visited=set()
                    self.dfs(grid,r,c,visited)
                    size=len(visited)
                    maxsize=max(maxsize,size)
                    for x,y in visited:
                        dp[x][y]=(isl_no,size)
                    cum_visited=cum_visited.union(visited)
                    isl_no+=1
                    #print (size,cum_visited)
        #print (dp)
        for r in range(nrows):
            for c in range(ncols):
                if grid[r][c]==0:
                    sz=self.join_zero(grid,dp,r,c)
                    maxsize=max(maxsize,sz)
        return maxsize
    
    def join_zero(self,grid,dp,r,c):
        islands=set()
        for nr,nc in [(r-1,c),(r,c-1),(r,c+1),(r+1,c)]:
            if nr>=0 and nr<len(grid) and nc>=0 and nc<len(grid[0]) and dp[nr][nc][1]!=0:
                islands.add(dp[nr][nc])
        if len(islands)==0: return 1
        
        #srt=list(islands)
        #srt.sort(key=lambda x:x[1])
        #print (r,c,srt)
        return sum(x[1] for x in islands)+1
                        
                    
    def dfs(self,grid,r,c,visited):
        visited.add((r,c))
        for n_r,n_c in [(r-1,c),(r,c-1),(r,c+1),(r+1,c)]:
            if n_r>=0 and n_r<len(grid) and n_c>=0 and n_c<len(grid[0]) and grid[n_r][n_c]==1 and (n_r,n_c) not in visited:
                self.dfs(grid,n_r,n_c,visited)
        


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def markIsland(grid, pos, root, d):
            i = pos[0]
            j = pos[1]
            if pos in d.get(root, set()):
                return
            if root not in d:
                d[root] = set()
            d[root].add(pos)
            
            if i > 0 and grid[i-1][j] == 1:
                markIsland(grid, (i-1,j), root, d)
            if i < len(grid) - 1 and grid[i+1][j] == 1:
                markIsland(grid, (i+1, j), root, d)
            if j > 0 and grid[i][j-1] == 1:
                markIsland(grid, (i, j-1), root, d)
            if j < len(grid[i]) - 1 and grid[i][j+1] == 1:
                markIsland(grid, (i, j+1), root, d)
            
            if pos == root:
                for entry in d[root]:
                    grid[entry[0]][entry[1]] = len(d[root])
            return
            
        def checkBranch(grid, pos, pos_dict, checked):
            def getSurrounding(grid, pos, pos_dict, checked):
                if pos in checked:
                    return checked[pos]
                visited = set()
                i = pos[0]
                j = pos[1]
                ret = 1
                if i > 0 and grid[i-1][j] != 0 and pos_dict[(i-1,j)] not in visited:
                    visited.add(pos_dict[(i-1,j)])
                    ret += grid[i-1][j]
                if i < len(grid) - 1 and grid[i+1][j] != 0 and pos_dict[(i+1,j)] not in visited:
                    visited.add(pos_dict[(i+1,j)])
                    ret += grid[i+1][j]
                if j > 0 and grid[i][j-1] != 0 and pos_dict[(i,j-1)] not in visited:
                    visited.add(pos_dict[(i,j-1)])
                    ret += grid[i][j-1]
                if j < len(grid[i]) - 1 and grid[i][j+1] != 0 and pos_dict[(i,j+1)] not in visited:
                    visited.add(pos_dict[(i,j+1)])
                    ret += grid[i][j+1]
                #print(pos, ret, checked, visited)
                checked[pos] = ret
                return ret
            
            
            i = pos[0]
            j = pos[1]
            max_connect = 1
            if i > 0 and grid[i-1][j] == 0:
                max_connect= max(max_connect, getSurrounding(grid, (i-1,j), pos_dict, checked))
            if i < len(grid) - 1 and grid[i+1][j] == 0:
                max_connect= max(max_connect, getSurrounding(grid, (i+1,j), pos_dict, checked))
            if j > 0 and grid[i][j-1] == 0:
                max_connect= max(max_connect, getSurrounding(grid, (i,j-1), pos_dict, checked))
            if j < len(grid[i]) - 1 and grid[i][j+1] == 0:
                max_connect= max(max_connect, getSurrounding(grid, (i,j+1), pos_dict, checked))
            return max_connect
            
        # mark total island sizes
        # { root: set(points in island) }
        d = dict()
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1:
                    markIsland(grid, (i,j), (i,j), d)
        #print(grid)
        
        max_size = 1
        pos_dict = dict()
        for key, value in d.items():
            max_size = max(max_size, len(value))
            for pos in value:
                pos_dict[pos] = key
        
        
        checked = dict()
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                max_size = max(max_size, checkBranch(grid, (i,j), pos_dict, checked))
        return max_size

class UF:
    def __init__(self, grid):
        N = len(grid[0]) * len(grid)
        self.parent = list(range(N))
        self.size = [0] * N
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]:
                    self.size[i * len(grid) + j] = 1

    def find(self, a):
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])
            self.parent[a] = self.parent[self.parent[a]]
        return self.parent[a]
    
    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa != pb:
            self.parent[pa] = pb
            self.size[pb] += self.size[pa]


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        uf = UF(grid)
        N, M = len(grid), len(grid[0])
        for i in range(N):
            for j in range(M):
                if not grid[i][j]:
                    continue
                for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < N and 0 <= ny < M and grid[nx][ny]:
                        uf.union(i * N + j, nx * N + ny)
        mx = 0
        for i in range(N):
            for j in range(M):
                if grid[i][j]:
                    continue
                all_adjacent = 0
                seen = set()
                for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < N and 0 <= ny < M and grid[nx][ny]:
                        parent = uf.find(nx * N + ny)
                        if parent not in seen:
                            seen.add(parent)
                            all_adjacent += uf.size[parent]
                mx = max(mx, 1 + all_adjacent)
        return max(mx, max(uf.size))

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        ROW, COL = len(grid), len(grid[0])
        labels = [ [0] * COL for _ in range(ROW) ]
        id = 0
        def neighbors(r, c):
            for nr, nc in ( (r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                if nr >= 0 and nr < ROW and nc >= 0 and nc < COL:
                    yield (nr, nc)
                    
        def dfs(row, col, id):
            if row < 0 or row >= ROW or col < 0 or col >= COL:
                return
            if labels[row][col] > 0 or grid[row][col] == 0:
                return
            labels[row][col] = id
            for (nr, nc) in neighbors(row, col):
                dfs(nr, nc, id)
            
        for row in range(ROW):
            for col in range(COL):
                if grid[row][col] == 1:
                    id += 1
                    dfs(row, col, id)
        
        size = collections.defaultdict(int)
        for row in range(ROW):
            for col in range(COL):
                id = labels[row][col]
                if id > 0:
                    size[id] += 1
        

        ans = max(list(size.values()) or [0])
        for row in range(ROW):
            for col in range(COL):
                if grid[row][col] == 1:
                    continue
                seen = { labels[nr][nc] for (nr, nc) in neighbors(row, col) if grid[nr][nc] == 1}
                ans = max(ans, 1 + sum( [size[id] for id in seen] ))
                          
        return ans
                
                    
                


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        '''
        Run DFS to find all islands (marked with unique id) and store their sizes. Then iterate through all zeros to see if a zero connects two islands. 
        DFS also counts the number of nodes in an island.
        
        Time O(N) - Run DFS to find all connected components takes O(N), and iterate through each zero takes O(1) for each because we only need to check the 4 neighbors of each zero. Total time O(N)
        Space O(N) - worst case, only additional storage is for island_sizes hashmap and zeros hashset, plus some constants.
        '''
        island_sizes = {}
        max_island_id, max_island_size = -1, 0
        # id starts from 2 to avoid conflict with 0/1
        global_island_id = 2
        zeros = set()
        deltas = ((1, 0), (-1, 0), (0, 1), (0, -1))
        rows, cols = len(grid), len(grid[0])
        
        def dfs(row, col, island_id) -> int:
            if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != 1:
                return 0
            count = 1
            grid[row][col] = island_id
            for dr, dc in deltas:
                count += dfs(row + dr, col + dc, island_id)
            return count
        
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 1:
                    cur_size = dfs(r, c, global_island_id)
                    island_sizes[global_island_id] = cur_size
                    if cur_size > max_island_size:
                        max_island_size = cur_size
                        max_island_id = global_island_id
                    global_island_id += 1
                elif val == 0:
                    zeros.add((r,c))
        
        if not zeros:
            return max_island_size
        
        for r, c in zeros:
            cur_max_size = 1
            islands_seen = set()
            for dr, dc in deltas:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    cur_val = grid[nr][nc]
                    if cur_val in island_sizes and cur_val not in islands_seen:
                        islands_seen.add(cur_val)
                        cur_max_size += island_sizes[cur_val]
            max_island_size = max(max_island_size, cur_max_size)
        
        return max_island_size

class DSU:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.cnt = N
    def find(self, i):
        if self.par[i] != i:
            self.par[i] = self.find(self.par[i])
        return self.par[i]
    def union(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            self.par[pi] = pj
            self.cnt-=1
        
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        R = len(grid)
        C = len(grid[0])
        dsu = DSU(R*C)
        dirs = [[1,0], [0,1],[-1,0], [0,-1]]
        for y in range(R):
            for x in range(C):
                if grid[y][x] == 1:
                    for dx,dy in dirs:
                        nx , ny = dx+x, dy+y
                        if 0<=nx<C and 0<=ny<R and grid[ny][nx] == 1:
                            dsu.union(y*R+x, ny*R+nx)
        smap = {}
        for y in range(R):
            for x in range(C):
                if grid[y][x] == 1:
                    r = dsu.find(y*R+x)
                    if r in smap:
                        smap[r] += 1
                    else:
                        smap[r] = 1
        ans = 0
        for y in range(R):
            for x in range(C):
                if grid[y][x] == 0:
                    rset = set()
                    for dx, dy in dirs:
                        nx , ny = dx+x, dy+y
                        if 0<=nx<C and 0<=ny<R and grid[ny][nx] == 1:
                            r = dsu.find(ny*R+nx)
                            rset.add(r)
                    t = 1
                    for r in rset:
                        t+=smap[r]
                    ans = max(ans, t)
        return ans if ans != 0 else R*C


class UnionFind:
    def __init__(self, N):
        self.parents = [i for i in range(N)]
        self.size = [1]*N

    def find(self, x):
        root = x
        while root != self.parents[root]:
            root = self.parents[root]

        while x != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent

        return root

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False

        if self.size[root_a] <= self.size[root_b]:
            self.parents[root_a] = root_b
            self.size[root_b] += self.size[root_a]
        else:
            self.parents[root_b] = root_a
            self.size[root_a] += self.size[root_b]

        return True

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        # assuming we have a UnionFind data structure
        
        def rc2idx(r, c):
            return r*n + c
        
        # build uf out of the islands
        uf = UnionFind(m*n)
        max_area = 0
        for r in range(m):
            for c in range(n):
                # union with the neighbours
                if grid[r][c] == 1:
                    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        nr, nc = r+dr, c+dc
                        if not (0 <= nr < m and 0 <= nc < n):
                            continue
                        if grid[nr][nc] == 1:
                            uf.union(rc2idx(r, c), rc2idx(nr, nc))
        
                    max_area = max(max_area, uf.size[uf.find(rc2idx(r, c))])
        
        # check all possible points for setting 0 to 1
        for r in range(m):
            for c in range(n):
                area = 0
                if grid[r][c] == 0:
                    area = 1
                    unique_neis = set()
                    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        nr, nc = r+dr, c+dc
                        if not (0 <= nr < m and 0 <= nc < n):
                            continue
                        if grid[nr][nc] == 1:
                            island = uf.find(rc2idx(nr, nc))
                            unique_neis.add(island)

                    area += sum([uf.size[island] for island in unique_neis])
    
                max_area = max(max_area, area)
        
        return max_area


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1]*n
    
    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
            
        while x != root:
            tmp = self.parent[x]
            self.parent[x] = root
            x = tmp
        return root
    
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
        
        if self.size[root_a] <= self.size[root_b]:
            self.parent[root_a] = root_b
            self.size[root_b] += self.size[root_a]
        else:
            self.parent[root_b] = root_a
            self.size[root_a] += self.size[root_b]
        
        return True
    
    
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
        m = len(grid)
        n = len(grid[0])
        uf = UnionFind(m*n)        
        # merge edges with 1-1
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 0:
                    continue
                
                rc = r*m+c
                for r_off, c_off in directions:
                    new_r, new_c = r+r_off, c+c_off
                    if not (0 <= new_r < len(grid) and 0 <= new_c < len(grid[0])):
                        continue
                    if grid[new_r][new_c] == 1:
                        new_rc = new_r*m+new_c
                        uf.union(rc, new_rc)
        
        max_area = max(uf.size)
        # try checking changing 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    continue
                    
                rc = r*m+c
                # id of neighbouring islands
                neighbours = set()
                for r_off, c_off in directions:
                    new_r, new_c = r+r_off, c+c_off
                    if not (0 <= new_r < len(grid) and 0 <= new_c < len(grid[0])):
                        continue
                    if grid[new_r][new_c] == 1:
                        new_rc = new_r*m+new_c
                        neighbours.add(uf.find(new_rc))
                
                max_area = max(max_area, 1 + sum([uf.size[i] for i in neighbours]))
        
        return max_area

class Solution(object):
    def largestIsland(self, grid):
        N = len(grid)

        def neighbors(r, c):
            for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                if 0 <= nr < N and 0 <= nc < N:
                    yield nr, nc

        def dfs(r, c, index):
            ans = 1
            grid[r][c] = index
            for nr, nc in neighbors(r, c):
                if grid[nr][nc] == 1:
                    ans += dfs(nr, nc, index)
            return ans

        area = {}
        index = 2
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    area[index] = dfs(r, c, index)
                    index += 1

        ans = max(area.values() or [0])
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
                    ans = max(ans, 1 + sum(area[i] for i in seen))
        return ans

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        ret=1
        size=[]
        direction=[(1,0),(0,1),(-1,0),(0,-1)]
        h=len(grid)
        w=len(grid[0])
        def dfs(y0,x0,mark):
            if grid[y0][x0]==1:
                grid[y0][x0]=mark
            inc=0
            cnt=0 
            seen=[]
            for y_offset,x_offset in direction:
                y1=y0+y_offset
                x1=x0+x_offset
                if 0<=x1<w and 0<=y1<h:
                    if grid[y0][x0]==0 and grid[y1][x1]<0 and grid[y1][x1]!=mark and grid[y1][x1] not in seen:
                        seen.append(grid[y1][x1])
                        inc+=size[-grid[y1][x1]-1]
                    elif grid[y0][x0]==mark and grid[y1][x1]>=0:
                        a,b=dfs(y1,x1,mark)
                        cnt+=a
                        inc=max(inc,b)
            print((cnt+(0 if grid[y0][x0]==0 else 1),inc+(1 if grid[y0][x0]==0 else 0)))
            return cnt+(0 if grid[y0][x0]==0 else 1),inc+(1 if grid[y0][x0]==0 else 0)
        idx=-1
        for y in range(h):
            for x in range(w):
                if grid[y][x]==1:
                    cnt,inc=dfs(y,x,idx)
                    size.append(cnt)
                    ret=max(ret,cnt+inc)
                    idx-=1
        return ret


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        \"\"\"
        Best explanation: https://www.youtube.com/watch?v=_426VVOB8Vo
        \"\"\"
        
        if not grid:
            return 0
        
        rows = len(grid)
        columns = len(grid[0])
        
        
        def dfsIslandSize(r, c, islandID, size):
            if r < 0 or r > rows - 1 or c < 0 or c > columns - 1 or grid[r][c] != 1:
                return size
            
            grid[r][c] = islandID
            size += 1
            
            size = dfsIslandSize(r-1, c, islandID, size)
            size = dfsIslandSize(r+1, c, islandID, size)
            size = dfsIslandSize(r, c-1, islandID, size)
            size = dfsIslandSize(r, c+1, islandID, size)
            
            return size
            
        
        def calculateJoinedIslandsSize(r, c):
            neighbors = set()
            
            if r - 1 >= 0 and grid[r-1][c] > 1:
                neighbors.add(grid[r-1][c])
                
            if c - 1 >= 0 and grid[r][c-1] > 1:
                neighbors.add(grid[r][c-1])
                
            if r + 1 <= rows - 1 and grid[r+1][c] > 1:
                neighbors.add(grid[r+1][c])
                
            if c + 1 <= columns - 1 and grid[r][c+1]:
                neighbors.add(grid[r][c+1])
                
            
            size = 1 # becouse we converted the current 0 to a 1
            for neighbor in list(neighbors):
                size += d[neighbor]
                
            return size                    
        

        
        islandID = 2
        d = {}
        maxSize = 0
        
        # Iterate first to mark grid with islandID and calculate island sizes
        for r in range(rows):
            for c in range(columns):
                if grid[r][c] == 1:
                    size = dfsIslandSize(r, c, islandID, 0)
                    d[islandID] = size
                    islandID += 1
                    maxSize = max(maxSize, size)
        
        # Iterate over grid. Convert 0 to 1 and calculate joined islands size
        for r in range(rows):
            for c in range(columns):
                if grid[r][c] == 0:
                    size = calculateJoinedIslandsSize(r, c)
                    maxSize = max(maxSize, size)
                    
        return maxSize
            
            
        

from collections import defaultdict, Counter
class Solution:
    def find(self, j):
        if self.d[j] == j:
            return j
        
        self.d[j] = self.find(self.d[j])
        return self.d[j]
    
    def union(self, ij1, ij2):
        i1 = self.find(ij1)
        i2 = self.find(ij2)
        if i1 == i2:
            return
        
        if self.rank[i2] > self.rank[i1]:
            self.d[i1] = i2
            # self.rank[i2] = self.rank[i1] + 1
        else:
            if self.rank[i1] >= self.rank[i2]:
                self.d[i2] = i1
            self.rank[i1] += 1
    
    def largestIsland(self, grid: List[List[int]]) -> int:
        self.rank, self.d = {}, {}
        self.z = []
        self.res = 1
        for r, row in enumerate(grid):
            for c, col in enumerate(row):
                if col == 1:
                    self.d[(r, c)] = (r, c)
                    self.rank[(r, c)] = 0
                if col == 0:
                    self.z.append((r, c))
                    
        for a, b in list(self.d.keys()):
            search = [(a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)]
            for c, d in search:
                if 0 <= c < len(grid) and 0 <= d < len(grid[0]) and grid[c][d] == 1:
                    self.union((a, b), (c, d))
        for key in list(self.d.keys()):
            self.find(key)
        cc = Counter(list(self.d.values()))
        if cc:
            self.res = max(cc.values())
        for a, b in self.z:
            search = [(a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)]
            total = {}
            for c, d in search:
                if 0 <= c < len(grid) and 0 <= d < len(grid[0]) and grid[c][d] == 1:
                    e, f = self.d[(c, d)]
                    total[(e, f)] = cc[(e, f)]
            print(('total ', total))
            s = sum(total.values())
            self.res = max(self.res, s + 1)
            
        return self.res


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        R = len(grid)
        C = len(grid[0])
        
        label = 2
       
        sum_of_area = 0
        max_area = 0
        map_info = {}
        # grid_info = copy.deepcopy(grid)
        
        for i in range(R):
            for j in range(C):
                if grid[i][j] == 1:
                    area = self.findIsland(grid, i, j, R, C, label)
                    map_info[label] = area
                    sum_of_area += area
                    label += 1
                
        print(map_info)    
        print(grid)
        
        for i in range(R):
            for j in range(C):
                if grid[i][j] == 0:
                    current = self.testChange(grid, i, j, R, C, map_info)
                    if current > max_area:
                        max_area = current
        
        if max_area == 0:
            max_area = sum_of_area
                
        return max_area
        
        
    def testChange(self, grid_info, i, j, R, C, map_info):
        
        island = []
        area = 0
        if 0 <= i+1 < R and grid_info[i+1][j] > 0:
            island.append(grid_info[i+1][j])
        
        if 0 <= i-1 < R and grid_info[i-1][j] > 0:
            island.append(grid_info[i-1][j])
        
        if 0 <= j+1 < C and grid_info[i][j+1] > 0:
            island.append(grid_info[i][j+1])
        
        if 0 <= j-1 < C and grid_info[i][j-1] > 0:
            island.append(grid_info[i][j-1])
            
        if not island: 
            return 1
        
        for key in list(map_info.keys()):
            if key in island:
                area += map_info[key]
                
        return area + 1
    
        
    def findIsland(self, grid, i, j, R, C, label):
        
        area = 0
        
        if  (i >= R or j >= C or i < 0 or j < 0) or grid[i][j] == 0 or grid[i][j] == label:
            return 0
        else:
            area = grid[i][j]
            grid[i][j] = label
            
            
        return area + self.findIsland(grid, i, j+1, R, C, label) + self.findIsland(grid, i, j-1, R, C, label) + self.findIsland(grid, i+1, j, R, C, label) + self.findIsland(grid, i-1, j, R, C, label)
        
            


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        N, M = len(grid), len(grid[0])
        visited = [[0]*M for _ in range(N)]
        group_ids_ = collections.defaultdict()
        group_counts_ = collections.Counter()
        _id_ = 0
        previous_count = 0
        for row in range(N):
            for col in range(M):
                if grid[row][col] == 1 and visited[row][col] == 0:
                    _id_ += 1
                    visited[row][col] = 1
                    stack = [(row, col)]
                    group_ids_[(row, col)] = _id_
                    while stack:
                        r, c = stack.pop()
                        for newr, newc in [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:
                            if 0<=newr<N and 0<=newc<M and visited[newr][newc]==0 and grid[newr][newc]==1:
                                visited[newr][newc] = 1
                                stack.append((newr,newc))
                                group_ids_[(newr,newc)] = _id_

                    group_counts_[_id_] = sum([sum(l) for l in visited]) - previous_count
                    previous_count = sum([sum(l) for l in visited])
        
        #print(group_ids_)
        #print(group_counts_)
        biggest = 0
        hasZero = False
        for r in range(N):
            for c in range(M):
                if grid[r][c] == 0:
                    hasZero = True
                    groups = set()
                    for newr, newc in [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:
                        if 0<=newr<N and 0<=newc<M and grid[newr][newc]==1:
                            groups.add(group_ids_[(newr,newc)])
                    biggest = max(biggest, sum([group_counts_[_id_] for _id_ in groups]) + 1)
        if hasZero:            
            return biggest
        else:
            return N*M
                        
                    
                    
                


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        '''
        Run DFS to find all islands (marked with unique id) and store their sizes. Then iterate through all zeros to see if a zero connects two islands.
        '''
        island_sizes = {}
        max_island_id, max_island_size = -1, 0
        # id starts from 2 to avoid conflict with 0/1
        global_island_id = 2
        zeros = set()
        deltas = ((1, 0), (-1, 0), (0, 1), (0, -1))
        rows, cols = len(grid), len(grid[0])
        
        def dfs(row, col, island_id) -> int:
            if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != 1:
                return 0
            count = 1
            grid[row][col] = island_id
            for dr, dc in deltas:
                count += dfs(row + dr, col + dc, island_id)
            return count
        
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 1:
                    cur_size = dfs(r, c, global_island_id)
                    island_sizes[global_island_id] = cur_size
                    if cur_size > max_island_size:
                        max_island_size = cur_size
                        max_island_id = global_island_id
                    global_island_id += 1
                elif val == 0:
                    zeros.add((r,c))
        
        if not zeros:
            return max_island_size
        
        for r, c in zeros:
            cur_max_size = 1
            islands_seen = set()
            for dr, dc in deltas:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    cur_val = grid[nr][nc]
                    if cur_val in island_sizes and cur_val not in islands_seen:
                        islands_seen.add(cur_val)
                        cur_max_size += island_sizes[cur_val]
            max_island_size = max(max_island_size, cur_max_size)
        
        return max_island_size

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        R = len(grid)
        C = len(grid[0])
        
        label = 2
       
        sum_of_area = 0
        max_area = 0
        map_info = {}
        # grid_info = copy.deepcopy(grid)
        
        for i in range(R):
            for j in range(C):
                if grid[i][j] == 1:
                    area = self.findIsland(grid, i, j, R, C, label)
                    map_info[label] = area
                    sum_of_area += area
                    label += 1
                
        print(map_info)    
        print(grid)
        
        for i in range(R):
            for j in range(C):
                if grid[i][j] == 0:
                    current = self.testChange(grid, i, j, R, C, map_info)
                    if current > max_area:
                        max_area = current
        
        if max_area == 0:
            max_area = sum_of_area
                
        return max_area
        
        
    def testChange(self, grid_info, i, j, R, C, map_info):
        
        island = []
        area = 0
        if 0 <= i+1 < R and grid_info[i+1][j] > 0:
            island.append(grid_info[i+1][j])
        
        if 0 <= i-1 < R and grid_info[i-1][j] > 0:
            island.append(grid_info[i-1][j])
        
        if 0 <= j+1 < C and grid_info[i][j+1] > 0:
            island.append(grid_info[i][j+1])
        
        if 0 <= j-1 < C and grid_info[i][j-1] > 0:
            island.append(grid_info[i][j-1])
            
        if not island: 
            return 1
        
        for key in list(map_info.keys()):
            if key in island:
                area += map_info[key]
                
        return area + 1
    
        
    def findIsland(self, grid, i, j, R, C, label):
        
        area = 0
        
        if  (i >= R or j >= C or i < 0 or j < 0) or grid[i][j] != 1:
            return 0
        else:
            area = grid[i][j]
            grid[i][j] = label
            
            
        return area + self.findIsland(grid, i, j+1, R, C, label) + self.findIsland(grid, i, j-1, R, C, label) + self.findIsland(grid, i+1, j, R, C, label) + self.findIsland(grid, i-1, j, R, C, label)
        
            


from collections import defaultdict, Counter
class Solution:
    def find(self, j):
        if self.d[j] == j:
            return j
        
        self.d[j] = self.find(self.d[j])
        return self.d[j]
    
    def union(self, ij1, ij2):
        i1 = self.find(ij1)
        i2 = self.find(ij2)
        if i1 == i2:
            return
        
        if self.rank[i2] > self.rank[i1]:
            self.d[i1] = i2
            # self.rank[i2] = self.rank[i1] + 1
        else:
            if self.rank[i1] >= self.rank[i2]:
                self.d[i2] = i1
            self.rank[i1] += 1
    
    def largestIsland(self, grid: List[List[int]]) -> int:
        self.rank, self.d = {}, {}
        self.z = []
        self.res = 1
        for r, row in enumerate(grid):
            for c, col in enumerate(row):
                if col == 1:
                    self.d[(r, c)] = (r, c)
                    self.rank[(r, c)] = 0
                if col == 0:
                    self.z.append((r, c))
                    
        for a, b in list(self.d.keys()):
            search = [(a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)]
            for c, d in search:
                if 0 <= c < len(grid) and 0 <= d < len(grid[0]) and grid[c][d] == 1:
                    self.union((a, b), (c, d))
        for key in list(self.d.keys()):
            self.find(key)
        cc = Counter(list(self.d.values()))
        print(('cc ', cc))
        
        print(('d ', self.d))
        print(('rank', self.rank))
        if cc:
            self.res = max(cc.values())
        for a, b in self.z:
            search = [(a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)]
            total = {}
            for c, d in search:
                if 0 <= c < len(grid) and 0 <= d < len(grid[0]) and grid[c][d] == 1:
                    e, f = self.d[(c, d)]
                    total[(e, f)] = cc[(e, f)]
            print(('total ', total))
            s = sum(total.values())
            self.res = max(self.res, s + 1)
            
        return self.res


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def method1():
            R=len(grid)
            if R<1:
                return 0
            C=len(grid[0])
            
            def neighbors(r,c):
                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:
                        yield nr,nc
            
            def dfs(r,c,visited):
                if (r,c) in seen:
                    return
                
                if grid[r][c]==0:
                    return
                
                seen.add((r,c))
                visited.add((r,c))
                for nr,nc in neighbors(r,c):
                    dfs(nr,nc,visited)
                    
            
            ans=float('-inf')
            seen=set()
            cc=[]
            zeros=set()
            
            for r in range(R):
                for c in range(C):
                    if grid[r][c]==1 and (r,c) not in seen:
                        visited=set()
                        dfs(r,c,visited)
                        if visited:
                            cc.append(visited)
                    
                    if grid[r][c]==0:
                        zeros.add((r,c))
                        
            if len(zeros)==R*C:
                return 1
                            
            ans=len(max(cc, key=len))
            for r,c in zeros:
                nei={(nr,nc) for nr,nc in neighbors(r,c)}
                
                if len(cc)==1:
                    if any((r,c) in cc[0] for r,c in nei):
                        ans=max(ans, len(cc[0])+1)
                else:
                    for i in range(len(cc)):
                        for j in range(i,len(cc)):
                            if (i!=j and any((r,c) in cc[i] for r,c in nei) and any((r,c) in cc[j] for r,c in nei)):
                                ans=max(ans, len(cc[i]) + len(cc[j]) + 1)
                        
            return ans
        #return method1()
    
        def method2():
            R=len(grid)
            if R<1:
                return 0
            C=len(grid[0])
            
            def neighbors(r,c):
                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:
                        yield nr,nc
                        
            def dfs(r,c,index):
                ans=1
                grid[r][c]=index
                for nr,nc in neighbors(r,c):
                    if grid[nr][nc]==1:
                        ans+=dfs(nr,nc,index)
                return ans
            
            area={}
            index=2
            for r in range(R):
                for c in range(C):
                    if grid[r][c]==1:
                        area[index]=dfs(r,c,index)
                        index+=1
                        
            ans=max(list(area.values()) or [0])
            for r in range(R):
                for c in range(C):
                    if grid[r][c]==0:
                        seen={grid[nr][nc] for nr,nc in neighbors(r,c) if grid[nr][nc]>1}
                        ans=max(ans, 1+sum(area[i] for i in seen))
                        
            return ans
        return method2()


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        def dfs(row, col, index):
            if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or grid[row][col] != 1:
                return 0
            grid[row][col] = index
            area = 1
            for direction in directions:
                area += dfs(row+direction[0], col+direction[1], index)
            return area
        
        max_area = 0
        found_zero = False
        visited = set()
        index = 2
        area = {}
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 1:
                    area[index] = dfs(row, col, index)
                    index += 1
        
        max_area = max(area.values() or [0])
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 0:
                    indexes = set()
                    for direction in directions:
                        new_row = row + direction[0]
                        new_col = col + direction[1]
                        if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and grid[new_row][new_col] > 1:
                            indexes.add(grid[new_row][new_col])
                        max_area = max(max_area, sum(area[index] for index in indexes) + 1)
                        
        return max_area

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        R = len(grid)
        C = len(grid[0])
        
        label = 1
       
        sum_of_area = 0
        max_area = 0
        map_info = {}
        grid_info = copy.deepcopy(grid)
        
        for i in range(R):
            for j in range(C):
                if grid[i][j] == 1:
                    area = self.findIsland(grid, grid_info, i, j, R, C, label)
                    map_info[label] = area
                    sum_of_area += area
                    label += 1
                
        print(map_info)
        print(grid_info)
        
        
        for i in range(R):
            for j in range(C):
                if grid_info[i][j] == 0:
                    current = self.testChange(grid_info, i, j, R, C, map_info)
                    if current > max_area:
                        max_area = current
        
        if max_area == 0:
            max_area = sum_of_area
                
        return max_area
        
        
    def testChange(self, grid_info, i, j, R, C, map_info):
        
        island = []
        area = 0
        if 0 <= i+1 < R and grid_info[i+1][j] > 0:
            island.append(grid_info[i+1][j])
        
        if 0 <= i-1 < R and grid_info[i-1][j] > 0:
            island.append(grid_info[i-1][j])
        
        if 0 <= j+1 < C and grid_info[i][j+1] > 0:
            island.append(grid_info[i][j+1])
        
        if 0 <= j-1 < C and grid_info[i][j-1] > 0:
            island.append(grid_info[i][j-1])
            
        if not island: 
            return 1
        
        for key in list(map_info.keys()):
            if key in island:
                area += map_info[key]
                
        return area + 1
        
    def findIsland(self, grid, grid_info, i, j, R, C, label):
        
        area = 0
        
        if  (i >= R or j >= C or i < 0 or j < 0) or grid[i][j] == 0:
            return 0
        else:
            area = grid[i][j]
            grid_info[i][j] = label
            grid[i][j] = 0
            
        return area + self.findIsland(grid, grid_info, i, j+1, R, C, label) + self.findIsland(grid, grid_info, i, j-1, R, C, label) + self.findIsland(grid, grid_info, i+1, j, R, C, label) + self.findIsland(grid, grid_info, i-1, j, R, C, label)
        
            


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return
        R,C = len(grid), len(grid[0])
        directions = [[0,1],[1,0],[0,-1],[-1,0]]
        d = collections.defaultdict(int)
        def dfs(grid,row,col,idx):
            grid[row][col] = idx
            total = 1
            for di in directions:
                newrow,newcol = row+di[0], col+di[1]
                if 0<=newrow<R and 0<=newcol<C and grid[newrow][newcol] ==1:
                    total += dfs(grid,newrow,newcol,idx)
            return total
                    
        index = 2
        maxlength = 0
        for i in range(R):
            for j in range(C):
                if grid[i][j] ==1:
                    total = 0
                    total = dfs(grid,i,j,index)
                    d[index] = total
                    maxlength = max(maxlength, total)
                    index +=1
        
        
        for i in range(R):
            for j in range(C):
                if grid[i][j] ==0:
                    keyset,length = set(),0
                    for di in directions:
                        newrow,newcol = i+di[0], j+di[1]
                    
                        if 0<=newrow<R and 0<=newcol<C and grid[newrow][newcol] > 1:
                            keyset.add(grid[newrow][newcol])
                    length = sum(d[key] for key in keyset)+1
                    maxlength = max(length,maxlength)
        
        return max(1,maxlength)
        
                            
        
        
                    


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        N = len(grid)
        M = len(grid[0])

        def neighbors(r, c):
            result = []
            for newR, newC in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                if 0 <= newR < N and 0 <= newC < M:
                    result.append((newR, newC))
            return result

        def dfs(r, c, index):
            ans = 1
            grid[r][c] = index
            for newR, newC in neighbors(r, c):
                if grid[newR][newC] == 1:
                    ans += dfs(newR, newC, index)
            return ans

        area = {}
        index = 2
        for r in range(N):
            for c in range(M):
                if grid[r][c] == 1:
                    area[index] = dfs(r, c, index)
                    index += 1

        ans = max(area.values() or [0])
        for r in range(N):
            for c in range(M):
                if grid[r][c] == 0:
                    seen = {grid[newR][newC] for newR, newC in neighbors(r, c) if grid[newR][newC] > 1}
                    ans = max(ans, 1 + sum(area[i] for i in seen))
        return ans

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        return self.largestIsland_dfs(grid)
        
        
    def largestIsland_dfs(self, grid: List[List[int]]) -> int:
        \"\"\"
        * Make eavery island a unqiue index (dfs, bfs)
        * Chehck every empty cell(0) to figure out largest area
        \"\"\"
        
        def moves(row, col):
            for rm, cm in (0, 1), (1, 0), (0, -1), (-1, 0):
                nr, nc = row + rm, col + cm
                if 0 <= nr < rows and 0 <= nc < cols:
                    yield nr, nc
        
        def dfs(row, col, index) -> int:
            grid[row][col] = index
            cur_size = 1
            for nr, nc in moves(row, col):
                if grid[nr][nc] != 1:
                    continue
                cur_size += dfs(nr, nc, index)
            return cur_size
        
        rows, cols = len(grid), len(grid[0])
        index = 2
        island_to_size = defaultdict(int)
        # island_to_size = {0:0} # edge case: input [[0,0],[0,0]]
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                size = dfs(r, c, index)
                island_to_size[index] = size
                index += 1
                
        # edge case: [[1,1], [1, 1]] or [[1]]
        # max_size = max(island_to_size.values())
        max_size = max(island_to_size.values()) if island_to_size else 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c]:
                    continue
                islands = set([grid[nr][nc] for nr, nc in moves(r, c)])
                cur_size = sum(island_to_size[idx] for idx in islands) + 1
                max_size = max(max_size, cur_size)
                
        return max_size
                

        

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        N = len(grid)
        
        def neighbours(r,c):
            result = []
            for nr, nc in [(r-1,c),(r+1,c),(r, c-1), (r, c+1)]:
                if 0 <= nr < N and 0 <= nc < N:
                    result.append((nr,nc))
            return result 
        
        def dfs(r, c, index):
            ans = 1 
            grid[r][c] = index
            for nr, nc in neighbours(r,c):
                if grid[nr][nc] == 1:
                    ans += dfs(nr, nc, index)
            return ans 
        
        areas = {}
        index = 2
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    areas[index] = dfs(r,c,index)
                    index += 1 
        ans = max(list(areas.values()) or [0])
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    seen = {grid[nr][nc] for nr, nc in neighbours(r,c) if grid[nr][nc] > 1}
                    ans = max(ans, 1 + sum(areas[i] for i in seen))
        
        return ans 
                    
        
                    
                    
        


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])

        max_size = 0

        # mark islands
        area_sizes = [0, 0]  # starts from  2

        def mark(i, j) -> int:  # size
            if not (0 <= i < M and 0 <= j < N):
                return 0
            if grid[i][j] != 1:
                return 0
            else:
                grid[i][j] = len(area_sizes)
            return 1 + mark(i - 1, j) + mark(i + 1, j) + mark(i, j - 1) + mark(i, j + 1)

        for i in range(M):
            for j in range(N):
                if grid[i][j] == 1:
                    area_sizes.append(mark(i, j))

        max_size = max(max_size, *area_sizes)  # FIXME: bug: 忘記考慮沒有 0 的狀況

        # for each 0, try to find max size
        for i in range(M):
            for j in range(N):
                if grid[i][j] == 0:
                    ids = set() # FIXME: bug: 忘記 dedup, 造成重複算
                    if 0 <= i - 1:
                        ids.add(grid[i - 1][j])
                    if i + 1 < M:
                        ids.add(grid[i + 1][j])
                    if 0 <= j - 1:
                        ids.add(grid[i][j - 1])
                    if j + 1 < N:
                        ids.add(grid[i][j + 1])

                    max_size = max(max_size, sum(area_sizes[id] for id in ids) + 1)

        return max_size


from typing import List
import math
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
      if grid == None or len(grid) == 0 or grid[0] == None or len(grid[0]) == 0:
        return 0
      n = len(grid)
      m = len(grid[0])
      compSize = [0]*(n*m + 2)
      def dfs(x, y, c):
        nonlocal compSize
        nonlocal grid
        compSize[c] += 1
        grid[y][x] = c
        nextPoints = [[x - 1, y],[x, y - 1],[x + 1, y],[x, y + 1]]
        for point in nextPoints:
          nextX = point[0]
          nextY = point[1]
          if nextX < 0 or nextX == m or nextY < 0 or nextY == n:
            continue
          if grid[nextY][nextX] == 1:
            dfs(nextX, nextY, c)
        return
      def calMaxLinkSize(x, y) -> int:
        nonlocal compSize
        nonlocal grid
        uniqueCompNums = []
        nextPoints = [[x - 1, y],[x, y - 1],[x + 1, y],[x, y + 1]]
        for point in nextPoints:
          nextX = point[0]
          nextY = point[1]
          if nextX < 0 or nextX == m or nextY < 0 or nextY == n:
            continue
          compNum = grid[nextY][nextX]
          if compNum >= 2 and compNum not in uniqueCompNums:
            uniqueCompNums.append(compNum)
        return sum([compSize[c] for c in uniqueCompNums]) + 1
      compNum =2
      maxCompSize = 0
      for y in range(n):
        for x in range(m):
          if grid[y][x] == 1:
            dfs(x, y, compNum)
            maxCompSize = max(maxCompSize, compSize[compNum])
            compNum += 1
      for y in range(n):
        for x in range(m):
          if grid[y][x] == 0:
            maxCompSize = max(maxCompSize, calMaxLinkSize(x, y))
      return maxCompSize
        



def __starting_point():
  pass
__starting_point()

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        # First DFS to find the each island and the island components. Then do another DFS to find out 
        # the size of the islands if the were to join.
        # TC = O(n^2), SC = O(n^2)
        
        m, n = len(grid), len(grid[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        def dfs(i, j):
            dic[(i, j)] = curr
            count[curr] += 1
            for dx, dy in directions:
                a, b = i + dx, j + dy
                if 0 <= a < m and 0 <= b < n and grid[a][b] == 1 and (a, b) not in dic:
                    dfs(a, b)

        def neighbours(i, j, adj):
            for dx, dy in directions:
                a, b = i + dx, j + dy
                if 0 <= a < m and 0 <= b < n and grid[a][b] == 1 and dic[(a, b)] not in adj:
                    adj.add(dic[(a, b)])
            
            return adj            
        
        curr, dic, count, res = 0, {}, collections.defaultdict(int), 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and (i, j) not in dic: 
                    curr += 1
                    dfs(i, j)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1: 
                    res = max(res, count[dic[(i, j)]])
                else:
                    res = max(res, sum(count[r] for r in neighbours(i, j, set())) + 1)
    
        return res

DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        N = len(grid)
        
        def move(x, y):
            ans = []
            for mv_x, mv_y in DIRECTIONS:
                x_ = x + mv_x
                y_ = y + mv_y
                if 0 <= x_ < N and 0 <= y_ < N:
                    ans.append((x_, y_))
            return ans
        
        # return area of the island
        def dfs(x, y, idx):
            ans = 1
            grid[x][y] = idx
            for i, j in move(x, y):
                if grid[i][j] == 1:
                    ans += dfs(i, j, idx)
            return ans
        
        idx = 2
        areas = {0: 0}
        for i in range(N):
            for j in range(N):
                if grid[i][j] == 1:
                    areas[idx] = dfs(i, j, idx)
                    idx += 1
        
        ans = max(areas.values())
        for i in range(N):
            for j in range(N):
                if grid[i][j] == 0:
                    cands = set(grid[x][y] for x, y in move(i, j))
                    ans = max(ans, sum(areas[idx] for idx in cands) + 1)
        return ans

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        parent = {}
        nums = collections.defaultdict(int)
        visited = set()
        res = 1
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1 and (i, j) not in parent:
                    parent[(i, j)] = (i, j)
                    stack = [(i, j)]
                    while stack:
                        x, y = stack.pop()
                        nums[(i, j)] += 1
                        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                        for direction in directions:
                            dx, dy = direction
                            if self.is_valid(grid, (x + dx, y + dy), parent):
                                parent[(x+dx, y+dy)] = (i, j)
                                stack.append((x + dx, y + dy))
        
        for v in list(nums.values()):
            res = max(res, v)
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    candidates = []
                    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                    for direction in directions:
                        dx, dy = direction
                        if i + dx < 0 or i + dx >= len(grid) or j + dy < 0 or j + dy >= len(grid[0]):
                            continue
                        # if (i+dx, j+dy) in visited:
                        #     continue
                        if grid[i+dx][j+dy] == 1:
                            continue
                        visited.add((i+dx, j+dy))
                        res = max(res, nums[parent[i, j]] + 1)
                        extra = 1
                        temp_visited = set()
                        for second_direction in directions:
                            ddx, ddy = second_direction
                            if i + dx + ddx < 0 or i + dx + ddx >=len(grid) or j + dy + ddy < 0 or j + dy + ddy >= len(grid[0]):
                                continue
                            if grid[i+dx+ddx][j+dy+ddy] == 0:
                                continue
                            if parent[(i+dx+ddx, j+dy+ddy)] == parent[(i, j)]:
                                continue
                            if parent[(i+dx+ddx, j+dy+ddy)] in temp_visited:
                                continue
                            else:
                                extra += nums[parent[i+dx+ddx, j+dy+ddy]]
                                temp_visited.add(parent[(i+dx+ddx, j+dy+ddy)])
                        
                        res = max(res, nums[parent[i, j]] + extra)
        
        return res
        
        
    def is_valid(self, grid, pos, parent):
        x, y = pos
        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
            return False
        if (x, y) in parent:
            return False
        if grid[x][y] == 0:
            return False
        
        return True
                    



class Solution:
    
    def largestIsland(self, grid):
        m, n, largest, areaMap = len(grid), len(grid[0]), 0, {}
        dirs = [[0,1], [0,-1], [-1,0], [1,0]]
        def getIsland(cords, cord):
            if cord[0] < 0 or cord[0] >= m or cord[1] < 0 or cord[1] >= n or not grid[cord[0]][cord[1]]: return
            if (cord[0], cord[1]) not in cords:
                cords.add(cord)
                for dir in dirs: getIsland(cords, (cord[0] + dir[0], cord[1] + dir[1]))
        # get {(i, j), set()} kind of map for each (i, j) where set includes all (i, j)s in the connected area
        for i in range(m):
            for j in range(n):
                if grid[i][j] and (i, j) not in areaMap:
                    cubes = set()
                    getIsland(cubes, (i, j))
                    largest = max(largest, len(cubes))
                    for c in cubes: areaMap[c] = cubes
        # traverse again to find any possible gap and walk thru the surrounding areas to find the largest
        for i in range(m):
            for j in range(n):
                if not grid[i][j]:
                    area, areaSet = 0, set()
                    for dir in dirs:
                        if (i + dir[0], j + dir[1]) in areaMap and (i + dir[0], j + dir[1]) not in areaSet:
                            area += len(areaMap[(i + dir[0], j + dir[1])])
                            areaSet |= areaMap[(i + dir[0], j + dir[1])]
                    largest = max(largest, area + 1)

        return largest
                        
                        
                    
                    
                        
                        
            
            


class Node:
    
    def __init__(self, row, col, parent=None):
        self.row = row
        self.col = col
        self.parent = parent or self
        self.rank = 0
        self.size = 1
    
    def __eq__(self, other):
        return other.row == self.row and other.col == self.col
    
    def __hash__(self):
        return hash((self.row, self.col))
    
    def __repr__(self):
        return f\"Node: {(self.row,self.col)}, Rank {self.rank}, Size {self.size}\"


class UnionFind:
    def __init__(self):
        self.count = 0
        self.rc_to_node = {}
        self.disjoint_sets=set()
    
    def find(self, row, col):
        
        val = (row,col)
        node = self.rc_to_node.get(val)
        if not node:
            node = Node(row,col)
            self.rc_to_node[val] = node
            self.disjoint_sets.add(node)
            self.count+=1
        elif node.parent != node:
            node.parent = self.find(node.parent.row, node.parent.col)
        
        return node.parent
    
    def union(self, fr,fc,sr,sc):
        first = self.find(fr,fc)
        second = self.find(sr,sc)
        
        if first == second:
            return
        
        if first.rank > second.rank:
            first,second = second, first
        
        first.parent = second
        second.rank+=first.rank == second.rank
        second.size+=first.size
        self.disjoint_sets.remove(first)
        self.count-=1
        #print(f\"{self.disjoint_sets}, {self.rc_to_node}\" )


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        direction = [(1,0),(0,1),(-1,0),(0,-1)]
        mrow,mcol = len(grid), len(grid[0])
        
        zero_indexes = []
        uf = UnionFind()
        for i, row in enumerate(grid):
            for j, col in enumerate(row):
                if not col:
                    zero_indexes.append((i,j))
                    continue
                uf.find(i,j)

                for dr,dc in direction:
                    r,c = dr+i, dc+j
                    if 0<=r<mrow and 0<=c<mcol and grid[r][c]:
                        uf.union(i,j,r,c)
        
        max_size = 0
        for c in uf.disjoint_sets:
            max_size = max(max_size,c.size)
        
        for i,j in zero_indexes:
            size = 0 
            parents = set()
            for dr,dc in direction:
                r,c = dr+i, dc+j
                if 0<=r<mrow and 0<=c<mcol and grid[r][c]:
                    node = uf.find(r,c)
                    if (node.row,node.col) not in parents:
                        size+=node.size
                        parents.add((node.row,node.col))
            
            max_size = max(max_size,size+1)
        
        return max_size
                        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

class Solution:
    def largestIsland(self, matrix: List[List[int]]) -> int:
        def move(r, c):
            for ri, ci in [[0,1], [1,0], [0,-1], [-1,0]]:
                rn, cn = r+ri, c+ci
                if 0 <= rn < len(matrix) and 0 <= cn < len(matrix[0]):
                    yield rn, cn
        def dfs(r, c, idx):
            res = 1
            matrix[r][c] = idx
            for rn, cn in move(r, c):
                if matrix[rn][cn] == 1:
                    res += dfs(rn, cn, idx)
            return res
        res = 0
        group = 2
        group_size = {0:0}
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 1:
                    count = dfs(i, j, group)
                    group_size[group] = count
                    res = max(res, count)
                    group += 1
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    # check adj 4
                    adjgrp = set(matrix[r][c] for r,c in move(i,j))
                    res = max(res, sum(group_size[grp] for grp in adjgrp)+1)
        return res            

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid: return 0
        
        M, N = len(grid), len(grid[0])
        size = [0, 0]
        
        for i in range(M):
            for j in range(N):
                if grid[i][j] == 1:
                    num = self.dfs(grid, i, j, len(size))
                    size.append(num)
                    
        #print(size)
        res = 0            
        for x0 in range(M):
            for y0 in range(N):
                if grid[x0][y0] == 0:
                    tmpSum = 1
                    tmpClr = set()
                    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                        x = x0 + dx
                        y = y0 + dy
                        if 0 <= x < M and 0 <= y < N:
                            tmpClr.add(grid[x][y])

                    for c in tmpClr:
                        tmpSum += size[c]
                        
                    res = max(res, tmpSum)
                      
        return res if res > 0 else M*N
    
    def dfs(self, grid, x0, y0, clr):
        grid[x0][y0] = clr
        res = 1
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            x = x0 + dx
            y = y0 + dy
            if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] == 1:
                res += self.dfs(grid, x, y, clr)
                
        return res
                    


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        nei = [(0,1),(1,0),(0,-1),(-1,0)]
        m, n = len(grid), len(grid[0])
        rec = dict()
        ans = 0
        def dfs(grid, i, j, color):
            cnt = 1
            grid[i][j] = color
            for dx, dy in nei:
                nx, ny = i + dx, j + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                    cnt += dfs(grid, nx, ny, color)
                    
            return cnt
        
        color = 2
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    temp = dfs(grid, i, j, color)
                    rec[color] = temp
                    color += 1
                    ans = max(ans, temp)
        
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    visit = set()
                    for dx, dy in nei:
                        nx, ny = i + dx, j + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != 0:
                            visit.add(grid[nx][ny])
                            
                    ans = max(ans, 1 + sum(rec[i] for i in visit))
           
        return ans
                    
        
        
        


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        # Time O(N^2) Space O(N^2)              
        if not grid or len(grid)==0: return 0
        nrows= len(grid)
        ncols= len(grid[0])
        islandid= 2
        maxsize= 0
        idsize= dict()
        
        def getIslandSize(grid, r, c, islandid):
            if not (0<=r<nrows and 0<=c<ncols) or grid[r][c]!=1:
                return 0
            grid[r][c]= islandid
            left= getIslandSize(grid, r, c-1, islandid)
            right= getIslandSize(grid, r, c+1, islandid)
            up = getIslandSize(grid, r-1, c, islandid)
            down= getIslandSize(grid, r+1, c, islandid)
            
            return left+right+up+down+1
        
        # DFS to assign unique islandid to all existing islands
        for r in range(nrows):
            for c in range(ncols):
                if grid[r][c]==1:
                    size= getIslandSize(grid, r, c, islandid)
                    maxsize= max(maxsize, size)
                    idsize[islandid]= size
                    islandid+=1
        
        
        # BFS to find if any 0 can be changed to 1 and find maxsize
        for r in range(nrows):
            for c in range(ncols):
                if grid[r][c]==0:
                    islands= set()
                    for direction in [[1,0], [0,1], [-1,0], [0,-1]]:
                        newr= r+direction[0]
                        newc= c+direction[1]
                        if 0<=newr<nrows and 0<=newc<ncols and grid[newr][newc]!=0:
                            islands.add(grid[newr][newc])
                    sum=1 # converted 0 to 1
                    for id in islands:
                        sum+=idsize[id]
                    maxsize= max(maxsize, sum)
                    
        return maxsize
                    
#   Only 2 steps:

# Explore every island using DFS, count its area, give it an island index and save the result to a {index: area} map.
# Loop every cell == 0, check its connected islands and calculate total islands area.


                
        
    


from collections import defaultdict
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def dfs(m, n, c_id):
            nonlocal grid, c_dict
            stack = [(m, n)]
            size = 1
            while stack:
                i, j = stack.pop()
                children = [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]
                for x, y in children:
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
                        grid[x][y] = c_id
                        size += 1
                        stack.append((x, y))
            c_dict[c_id] = size
        c_id = 1
        c_dict = defaultdict(int)
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    c_id += 1
                    grid[i][j] = c_id
                    dfs(i, j, c_id)
        result = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] > 0: continue
                children = [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]
                n_c = set()
                for x, y in children:
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] > 0:
                        n_c.add(grid[x][y])
                result = max(result, sum([c_dict[c] for c in n_c]) + 1)
        return result if result > 0 else len(grid) * len(grid[0])

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        N = len(grid)

        def neighbors(r,c):
            for nr, nc in [(r-1,c),  (r,c-1),(r+1,c),(r,c+1)]:
                if 0 <= nr < N and 0 <= nc < N:
                    yield nr,nc
        
        
        def dfs(r,c, index):
            ans = 1
            grid[r][c] = index
            for nr, nc in neighbors(r,c):
                if grid[nr][nc] == 1:
                    ans += dfs(nr, nc, index)
            return ans
        
            
        area = {}
        index = 2
        N = len(grid)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    area[index] = dfs(r,c, index)
                    index += 1
        
        
        
        ans = max(area.values() or [0])
        
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    seen = {grid[nr][nc] for nr,nc in neighbors(r,c) if grid[nr][nc] > 1}
                    ans = max(ans, 1+sum(area[i] for i in seen))
                
        return ans