Union Find
1 in an island is like an element in a disjoint set; an island is like a disjoint set. So we may use Disjoint Set (a.k.a. Union Find) to model the problem first
`1` in an island is like an element in a disjoint set; an island is like a disjoint set. So we may use Disjoint Set (a.k.a. Union Find) to model the problem first. For every `1` encountered in the grid, we perform a union operation with its adjacent `1`s.\n\nAfter modeling the problem, for each `0`, we consider the result of "flipping" it to a `1` and calculate the size of the island that would result from this change. This involves checking the `0`\'s four adjacent cells, identifying **distinct** islands adjacent to this cell, and summing their sizes (+1 for the "flipped" cell itself) to calculate the potential island size.\n\nTime complexity: `O(n*n)`\n\nSpace complexity: `O(n*n)`\n\n\n```\nclass Solution:\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        n = len(grid)\n        uf = UnionFind(n * n)\n        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n\n        def id(x, y):\n            return x * n + y\n\n        for i in range(n):\n            for j in range(n):\n                if grid[i][j] == 1:  # union around\n                    for dx, dy in dirs:\n                        ni, nj = i + dx, j + dy\n                        if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1:\n                            uf.union(id(ni, nj), id(i, j))\n        \n        max_sz = 0\n        for i in range(n):\n            for j in range(n):\n                root = uf.find(id(i, j))\n                max_sz = max(max_sz, uf.size[root])\n\n        \n        for i in range(n):\n            for j in range(n):\n                if grid[i][j] == 0:\n                    sz = 1  # Start with 1 for the flipped cell\n                    root_set = set()  # Ensure distinct adjacent islands\n                    for dx, dy in dirs:\n                        ni, nj = i + dx, j + dy\n                        if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1:\n                            root = uf.find(id(ni, nj))\n                            if root not in root_set:\n                                sz += uf.size[root]\n                                root_set.add(root)\n                        max_sz = max(max_sz, sz)\n        return max_sz\n\n\n\nclass UnionFind:\n    def __init__(self, n: int):\n        self.parent = list(range(n))\n        self.size = [1] * n\n\n    def find(self, i):\n        if self.parent[i] != i:\n            self.parent[i] = self.find(self.parent[i])\n        return self.parent[i]\n\n    def union(self, x, y):\n        root_x = self.find(x)\n        root_y = self.find(y)\n        if root_x != root_y:\n            if self.size[root_y] > self.size[root_x]:\n                self.parent[root_x] = root_y\n                self.size[root_y] += self.size[root_x]\n            else:\n                self.parent[root_y] = root_x\n                self.size[root_x] += self.size[root_y]                \n\n```
['Union Find', 'Python']