"""
827
hard
making a large island

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

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

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


from typing import List


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

        # union find

        islands = {}
        size = {}
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                islands[i, j] = None        # not part of islands

        def find(g):
            while islands[g] is not g:
                g = islands[g]
                if g is None:
                    break
            return g

        def union(g1, g2):
            c1, c2 = find(g1), find(g2)
            if c1 != c2:
                if size[c1] < size[c2]:
                    c1, c2 = c2, c1
                islands[c2] = c1
                size[c1] += size[c2]
                del size[c2]

        visited = set()

        def dfs(g, parent):
            if g[0] < 0 or g[0] >= m or g[1] < 0 or g[1] >= n or grid[g[0]][g[1]] == 0:
                return
            if g in visited:
                return
            union(g, parent)
            visited.add(g)

            dfs((g[0] - 1, g[1]), parent)
            dfs((g[0] + 1, g[1]), parent)
            dfs((g[0], g[1] - 1), parent)
            dfs((g[0], g[1] + 1), parent)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    islands[i, j] = (i, j)  # create new island
                    size[i, j] = 1

        for i in range(m):
            for j in range(n):
                if (i, j) not in visited and grid[i][j] == 1:
                    dfs((i, j), (i, j))

        if size:
            max_size = max(size[key] for key in size)
        else:
            return 1

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    neighbors = set()
                    for x, y in (i-1, j), (i+1, j), (i, j-1), (i, j+1):
                        if 0 <= x <= m-1 and 0 <= y <= n-1:
                            island = find((x, y))
                            if island is not None:
                                neighbors.add(island)
                        total_size = 0
                        for neighbor in neighbors:
                            total_size += size[neighbor]
                        max_size = max(max_size, total_size+1)

        return max_size


grid = [[1,1],[1,1]]
grid2 = [[0,0],[1,0]]
sol = Solution()
print(sol.largestIsland(grid2))









