Skip to main content

Matrices

Connected Components​

200. Number of Islands​

Medium·
Explanation

Map each cell (row, col) to a flat DSU index via row * n + col. Initialize island_count = 0. Scan left-to-right, top-to-bottom: for every '1' cell, increment island_count. Then union it with any already-seen '1' neighbor above or to the left -- each successful union() returns True (1 in Python), so island_count -= union(...) effectively decrements the count when two previously separate islands merge into one.

Analysis
Time
O(m * n * α(m * n))
  • The nested for row / for col loop visits every one of the m * n cells exactly once.
  • Each '1' cell makes at most two union calls (up, left), each an amortized α(m * n) with path compression and union by rank - m * n * α(m * n).
Space
O(m * n)
  • DisjointSets's parent, rank, and size arrays are each sized n * m.
FIG. NUMBER OF ISLANDS DSU● INTERACTIVE
visualization loads as you reach it
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·
Explanation

Map each cell (row, col) to a flat DSU index via row * n + col. Scan left-to-right, top-to-bottom: for every 1 cell, union it with any already-seen 1 neighbor above or to the left. After all unions for that cell, call getSize(idx) -- which does size[find(idx)] -- to read the current component's size. Track the running maximum across all cells.

Analysis
Time
O(m*n*α(m*n))
  • m and n are the grid's row and column counts. The nested for row/for col loops visit each of the m*n cells once.
  • Each union/find call (and the getSize call, which invokes find internally) costs O(α(m*n)) amortized with path compression and union by rank.
Space
O(m*n)
  • The DSU's parent, rank, and size arrays are each sized m*n (one entry per cell).
FIG. MAX AREA OF ISLAND DSU● INTERACTIVE
visualization loads as you reach it
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