We’re asked to determine the number of islands in a 2D matrix of “1”s and “0”s. “1”s represent land, and islands are adjacent “1”s in the directions up, down, left, and right. This question essentially asks us to find the connected components for the nodes represented by “1”s in this 2D matrix. Nodes are connected if adjacent nodes are “1”s as well.
To solve this connectivity problem, we use Union-Find again. We maintain a parent and rank array in the Union-Find class, doing a little extra work to create a hash map that we can index into with our custom hashing function:
i * m + j
where i and j are the row and column indices, and m is the number of columns in the 2D matrix.
When evaluating each node in the 2D matrix, we check to see if the current i, j matrix location contains a “1”. If so, we mark the location as seen by changing the value to “0”. We then check all adjacent locations to see if they’re valid nodes containing a “1”. If these adjacent locations are connected to the current node, we merge their sets together.
Each time we execute union_set, we decrement the number of islands by 1. This is because we’re merging connected components together, and the number of connected components is the number of islands.
The solution is as follows:
from collections import defaultdict
class UnionFind:
def __init__(self, grid: List[List[str]]) -> None:
self.count = 0
n, m = len(grid), len(grid[0])
self.parent, self.rank = [0 for _ in range(n - m)], [0 for _ in range(n * m)]
for i in range(n):
for j in range(m):
if grid[i][j] == "1":
self.parent[i * m + j] = i * m + j
self.count += 1
self.rank[i * m + j] = 0
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union_set(self, x: int, y: int) -> None:
xset, yset = self.find(x), self.find(y)
if xset != yset:
if self.rank[xset] < self.rank[yset]:
self.parent[xset] = yset
elif self.rank[yset] < self.rank[xset]:
self.parent[yset] = xset
else:
self.parent[yset] = xset
self.rank[xset] += 1
self.count -= 1
def get_count(self) -> int:
return self.count
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
dsu = UnionFind(grid)
for i in range(n):
for j in range(m):
if grid[i][j] == "1":
grid[i][j] = "0"
if i - 1 > -1 and grid[i - 1][j] == "1":
dsu.union_set(i * m + j, (i - 1) * m + j)
if i + 1 < n and grid[i + 1][j] == "1":
dsu.union_set(i * m + j, (i + 1) * m + j)
if j - 1 > -1 and grid[i][j - 1] == "1":
dsu.union_set(i * m + j, i * m + (j - 1))
if j + 1 < m and grid[i][j + 1] == "1":
dsu.union_set(i * m + j, i * m + (j + 1))
return dsu.get_count()_ Time Complexity:
O(n * m) - We iterate over all values in the 2D matrix.
_ Space Complexity:
O(n * m) - We maintain the parent and rank arrays.