<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, grid: List[List[str]]):
        self._count = 0
        self._parent = []
        self._rank = []
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == "1":
                    cell_index = row * len(grid[0]) + col
                    self._parent.append(cell_index)
                    self._count += 1
                else:
                    self._parent.append(-1)
                self._rank.append(0)

    def find(self, data: int) -> int:
        if self._parent[data] != data:
            self._parent[data] = self.find(self._parent[data])
        return self._parent[data]

    def union(self, a: int, b: int) -> None:
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            if self._rank[root_a] > self._rank[root_b]:
                self._parent[root_b] = root_a
            elif self._rank[root_a] < self._rank[root_b]:
                self._parent[root_a] = root_b
            else:
                self._parent[root_b] = root_a
                self._rank[root_a] += 1
            self._count -= 1

    def count(self) -> int:
        return self._count


class Solution:
    @staticmethod
    def _combine_lands(grid: List[List[str]], uf: UnionFind, pos: tuple[int, int], pos_new: tuple[int, int]) -> None:
        r_new, c_new = pos_new
        if r_new < 0 or c_new < 0:
            return
        if r_new > len(grid) - 1 or c_new > len(grid[0]) - 1:
            return
        if grid[r_new][c_new] == "0":
            return
        r, c = pos
        pos_index = r * len(grid[0]) + c
        pos_new_index = r_new * len(grid[0]) + c_new
        uf.union(pos_index, pos_new_index)

    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        rows = len(grid)
        cols = len(grid[0])
        uf = UnionFind(grid)

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == "0":
                    continue
                grid[row][col] = "0"
                self._combine_lands(grid, uf, (row, col), (row - 1, col))
                self._combine_lands(grid, uf, (row, col), (row + 1, col))
                self._combine_lands(grid, uf, (row, col), (row, col - 1))
                self._combine_lands(grid, uf, (row, col), (row, col + 1))
        return uf.count()
22003