<p>You are given an <code>n x n</code> binary matrix <code>grid</code>. You are allowed to change <strong>at most one</strong> <code>0</code> to be <code>1</code>.</p>

<p>Return <em>the size of the largest <strong>island</strong> in</em> <code>grid</code> <em>after applying this operation</em>.</p>

<p>An <strong>island</strong> is a 4-directionally connected group of <code>1</code>s.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0],[0,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,0]]
<strong>Output:</strong> 4
<strong>Explanation: </strong>Change the 0 to 1 and make the island bigger, only one island with area = 4.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Can&#39;t change any 0 to 1, only one island with area = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class UnionFind():
    #go through grid
    #1. add points to par and rank
    #2. go through neighbors, and if touching, then union
    def __init__(self, grid):
        self.par = {}
        self.rank = {}

        M,N = len(grid),len(grid[0])
        for i in range(M):
            for j in range(N):
                if grid[i][j]:
                    pt = (i,j)
                    self.par[pt] = pt
                    self.rank[pt] = 1


        D = [(-1,0),(1,0),(0,1),(0,-1)]
        def inbound(pt):
            return M > pt[0] >= 0 <= pt[1] < N

        #connects the grid
        for i in range(M):
            for j in range(N):
                if grid[i][j]:
                    pt = (i,j)
                    neighbors = [(i+d[0],j+d[1]) for d in D]
                    for n in neighbors:
                        if inbound(n) and grid[n[0]][n[1]]:
                            self.union(pt,n)
                    #self.find(pt)

    def find(self,x):
        if x != self.par[x]:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self,x,y):
        X,Y = self.find(x),self.find(y)

        if X == Y: 
            return False
        else:
            rX,rY = self.rank[X],self.rank[Y]

            if rX < rY: #join x onto y
                self.par[X] = Y
                self.rank[Y] += rX
                #self.rank[X] = 0
                del self.rank[X]
            else:
                self.par[Y] = X
                self.rank[X] += rY
                #self.rank[Y] = 0
                del self.rank[Y]

            return True


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

        
        uf = UnionFind(grid)

        M,N = len(grid),len(grid[0])
        def inbound(pt):
            return M > pt[0] >= 0 <= pt[1] < N

        D = [(-1,0),(1,0),(0,1),(0,-1)]

        maxSize = -inf

        for i in range(M):
            for j in range(N):
                if not grid[i][j]:  #this is a 0

                    neighbors = [(i+d[0],j+d[1]) for d in D]
                    seen = set()
                    size = 1
                    for n in neighbors:
                        if inbound(n) and grid[n[0]][n[1]]:
                            p = uf.find(n)
                            if not p in seen:
                                size += uf.rank[p]  #add area
                                seen.add(p)         #cannot re-visit this same parent any more

                    maxSize = max(maxSize,size)
                    if maxSize == M*N:
                        return maxSize

        return maxSize if maxSize > -inf else M*N


        #go through each 0 point, if it is 1, it SHOULD connect all the neighbors
        #for 




        return -1














class UnionFindKD():
    def __init__(self,grid):
        self.par = {}
        self.rank = {}
        self.directions = [(1,0),(-1,0),(0,1),(0,-1)]
        self.grid = grid
        self.M,self.N = len(self.grid),len(self.grid[0])

        for i in range(self.M):
            for j in range(self.N):
                if grid[i][j]:
                    self.add((i,j))

    def inbound(self, pt):
        return self.M > pt[0] >= 0 <= pt[1] < self.N

    def add(self, pt):
        #add point
        #look through neighbors to union pt with neighbors
        #print("Adding", pt)
        if not pt in self.par:
            self.par[pt] = pt
            self.rank[pt] = 1

            neighbors = [(pt[0]+d[0], pt[1]+d[1]) for d in self.directions]
            for n in neighbors:
                if self.inbound(n) and self.grid[n[0]][n[1]] and n in self.par:
                    self.union(pt,n)


    def find(self, n):
        #print(n, self.par)
        if self.par[n] != n:
            self.par[n] = self.find(self.par[n])
        return self.par[n]

    def union(self, x, y):
        px,py = self.find(x),self.find(y)

        if px == py:
            return False

        rx,ry = self.rank[px],self.rank[py]

        if rx >= ry:
            self.par[py] = px
            self.rank[px] += self.rank[py]
            #self.rank[py] = 0
        else:
            self.par[px] = py
            self.rank[py] += self.rank[px]
            #self.rank[px] = 0

        return True


class SolutionKD:
    def largestIslandKD(self, grid: List[List[int]]) -> int:

        M,N = len(grid),len(grid[0])

        uf = UnionFind(grid)
        directions = [(1,0),(-1,0),(0,1),(0,-1)]

        def inbound(pt):
            return M > pt[0] >= 0 <= pt[1] < N

        maxSize = max(uf.rank.values()) if uf.rank else 0
        
        for i in range(M):
            for j in range(N):
                if grid[i][j]==0:                   
                    neighbors = [(i+d[0],j+d[1]) for d in directions]
                    
                    currSize = 1
                    seen = set()
                    for n in neighbors:
                        if inbound(n) and grid[n[0]][n[1]] and not uf.find(n) in seen:
                            seen.add(uf.find(n))
                            currSize += uf.rank[uf.find(n)]
                            
                    maxSize = max(maxSize, currSize)

        return maxSize
46056