Python Union Find AC with Explanation in Code Comments
\nclass Solution(object):\n    def largestIsland(self, grid):\n        """\n        :type grid: List[List[int]]\n        :rtype: int\n        """\n        if no
```\nclass Solution(object):\n    def largestIsland(self, grid):\n        """\n        :type grid: List[List[int]]\n        :rtype: int\n        """\n        if not grid or not grid[0]: return 0\n        # First do a regular union find to find all the islands and their sizes, remember the biggest island\'s size in \'biggest\'.\n        # Also remember all zero positions\n        uf={}\n        size={}\n        rank={}\n        zeros=[]\n        biggest=0\n        def findparent(x):\n            if x not in uf: return x\n            if uf[x]!=x: return findparent(uf[x])\n            return x\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j]==0:\n                    zeros.append((i,j))\n                    continue\n                if (i,j) not in uf:\n                    uf[(i,j)]=(i,j)\n                    rank[(i,j)]=0\n                    size[(i,j)]=1\n                    biggest=max(biggest,1)\n                for ni,nj in [(i-1,j),(i,j-1)]:\n                    if 0<=ni<len(grid) and 0<=nj<len(grid[0]) and (ni,nj) in uf:\n                        parA=findparent((i,j))\n                        parB=findparent((ni,nj))\n                        if parA!=parB:\n                            if rank[parA]>rank[parB]:\n                                uf[parB]=parA\n                                rank[parA]+=1\n                                size[parA]+=size[parB]\n                                biggest=max(biggest,size[parA])\n                            else:\n                                uf[parA]=parB\n                                rank[parB]+=1\n                                size[parB]+=size[parA]\n                                biggest=max(biggest,size[parB])\n        # Now loop over the zeros, and check all of its \'1\' neighbors, and tally their sizes in \'neisizes\'\n        # If this new \'1\' connects multiple previously separated islands, the new island\'s size would be sum(neisizes)+1\n        for i,j in zeros:\n            neisizes=[]\n            visited=set()\n            for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n                if 0<=ni<len(grid) and 0<=nj<len(grid[0]) and (ni,nj) in uf:\n                    par=findparent((ni,nj))\n                    if par not in visited:\n                        neisizes.append(size[par])\n                        visited.add(par)\n            biggest=max(biggest,sum(neisizes)+1)\n        return biggest\n```
[]