<p>Given an <code>m x n</code> 2D binary grid <code>grid</code> which represents a map of <code>&#39;1&#39;</code>s (land) and <code>&#39;0&#39;</code>s (water), return <em>the number of islands</em>.</p>

<p>An <strong>island</strong> is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.</p>

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

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]
]
<strong>Output:</strong> 1
</pre>

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

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]
]
<strong>Output:</strong> 3
</pre>

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

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>grid[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class UnionFind:
    def __init__(self,n):
        self.root = [i for i in range(n)]
        self.rank = [1] *n
    
    def find(self,x):
        if(self.root[x]==x):
            # reach parent:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self,x,y):
        rootX,rootY = self.find(x),self.find(y)
        if(rootX!=rootY):
            # we will union
            if(self.rank[rootX]>self.rank[rootY]):
                # add small to big tree
                self.root[rootY] = rootX
            elif(self.rank[rootX]<self.rank[rootY]):
                self.root[rootX] = rootY
            else:
                # when the 2 trees are the same
                self.root[rootY] = rootX
                self.rank[rootX]+=1

    def isConnect(self,x,y):
        return self.find(x)==self.find(y)

    def countIslands(self):
        n= len(self.root)
        ans = 0 
        roots ={}
        for i in range(n):
            r = self.find(i)
            if r not in roots:
                roots[r]=1
            else:
                roots[r]+=1

        
        return 1

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m,n = len(grid),len(grid[0])
        total = m*n
        uf = UnionFind(total)
        lands = []
        for i in range(m):
            for j in range(n):
                if(grid[i][j]=="1"):
                    lands.append((i,j))
                    fourDir = self.getFourDir(i,j,grid)
                    curIndex = self.getIndex(i,j,grid)
                    for f in fourDir:
                        nextI,nextJ = f[0],f[1]
                        nextI = self.getIndex(nextI,nextJ,grid)
                        uf.union(curIndex,nextI)
        
        islands = {}
        ans = 0 
        for land in lands:
            index = self.getIndex(land[0],land[1],grid)
            root = uf.find(index)
            if(root not in islands):
                ans+=1
                islands[root]=1

        return ans
                        
    
    def getIndex(self,i,j,grid):
        #convert the i,j to flat index in the union find array
        n,m = len(grid),len(grid[0])
        ans = m*i+j
        return ans

    def getFourDir(self,i,j,grid):
        #return valid next moves base on current location

        m,n = len(grid),len(grid[0])
        dirs = []
        if(i>0):
            dirs.append((i-1,j))
        if(i<m-1):
            dirs.append((i+1,j))
        if(j>0):
            dirs.append((i,j-1))
        if(j<n-1):
            dirs.append((i,j+1))
        
        ans = []
        for d in dirs:
            x,y = d[0],d[1]
            if(grid[x][y]=="1"):
                ans.append(d)
        return ans
25581