Matrices
Connected Components
200. Number of Islands
Medium·
Solutions:
Visualize
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
def getCount(self):
return self.count
def getSize(self, a):
return self.size[self.find(a)]
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
disjoint_sets = DisjointSets(n * m)
island_count = 0
getIdx = lambda row, col: row * n + col
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isIsland = lambda row, col: isValidCell(row, col) and grid[row][col] == "1"
for row in range(m):
for col in range(n):
if isIsland(row, col):
island_count += 1
if isIsland(row - 1, col):
island_count -= disjoint_sets.union(
getIdx(row, col), getIdx(row - 1, col)
)
if isIsland(row, col - 1):
island_count -= disjoint_sets.union(
getIdx(row, col), getIdx(row, col - 1)
)
return island_count
Component Size
695. Max Area of Island
Medium·
Solutions:
Visualize
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
def getCount(self):
return self.count
def getSize(self, a):
return self.size[self.find(a)]
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
disjoint_sets = DisjointSets(n * m)
getIdx = lambda row, col: row * n + col
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isIsland = lambda row, col: isValidCell(row, col) and grid[row][col] == 1
max_size = 0
for row in range(m):
for col in range(n):
if isIsland(row, col):
idx = getIdx(row, col)
if isIsland(row - 1, col):
disjoint_sets.union(idx, getIdx(row - 1, col))
if isIsland(row, col - 1):
disjoint_sets.union(idx, getIdx(row, col - 1))
max_size = max(max_size, disjoint_sets.getSize(idx))
return max_size