<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 Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nRows = len(grid)
        nCols = len(grid[0])
        nTotal = nRows * nCols

        def getIdx(row, col):
            return row * nCols + col

        def isIsland(n):
            row = n // nCols
            col = n % nCols
            return grid[row][col] == "1"

        parents = [i if isIsland(i) else -1 for i in range(nTotal)]
        ranks = [0 if isIsland else -1 for i in range(nTotal)]

        def find(x):
            parentX = parents[x]
            if x != parentX:
                parentX = find(parentX)
                parents[x] = parentX
            return parentX

        def union(x, y):
            parentX = find(x)
            parentY = find(y)
            if parentX == parentY:
                return
            rankX = ranks[x]
            rankY = ranks[y]
            if rankX > rankY:
                parents[parentY] = parentX
                ranks[parentY] += 1
            else:
                parents[parentX] = parentY
                ranks[parentX] += 1

        for row in range(nRows):
            for col in range(nCols):
                n = getIdx(row, col)
                if not isIsland(n):
                    continue
                if row < nRows - 1:
                    adjN = getIdx(row + 1, col)
                    if isIsland(adjN):
                        union(n, adjN)
                if col < nCols - 1:
                    adjN = getIdx(row, col + 1)
                    if isIsland(adjN):
                        union(n, adjN)

        islands = set()
        for row in range(nRows):
            for col in range(nCols):
                n = getIdx(row, col)
                if not isIsland(n):
                    continue
                islands.add(find(n))
        return len(islands)

21076