# Number of Islands

BFSDFSUnion Find

## # Solution

Let $n$ be the number of rows and $m$ be the number of columns.

### # BFS

Complexity

time: $O(V + E) = O(nm)$
space: $O(V + E) = O(nm)$

DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def numIslands(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
queue = []
res = 0

def bfs(i, j):
queue = [(i, j)]
grid[i][j] = '0'

while queue:
x, y = queue.pop(0)
for dx, dy in DIRECTIONS:
nx, ny = x+dx, y+dy
if 0 <= nx < n and 0 <= ny < m and grid[nx][ny]=='1':
grid[nx][ny] = '0'
queue.append((nx, ny))

for i in range(n):
for j in range(m):
if grid[i][j] == '1':
bfs(i, j)
res += 1
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

### # DFS

Complexity

time: $O(V + E) = O(nm)$
space: $O(V + E) = O(nm)$

DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def numIslands(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
queue = []
res = 0

def dfs(i, j):
queue = [(i, j)]
grid[i][j] = '0'

while queue:
x, y = queue.pop()
for dx, dy in DIRECTIONS:
nx, ny = x+dx, y+dy
if 0 <= nx < n and 0 <= ny < m and grid[nx][ny]=='1':
grid[nx][ny] = '0'
queue.append((nx, ny))

for i in range(n):
for j in range(m):
if grid[i][j] == '1':
dfs(i, j)
res += 1
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

### # Union Find

See more in Interview Algorithms.

DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
class UnionFind:
def __init__(self, grid):
n, m = len(grid), len(grid[0])
self.count = 0
self.parent = [-1 for _ in range(n*m)]
self.rank = [0 for _ in range(n*m)]
for i in range(n):
for j in range(m):
if grid[i][j] == '1':
self.parent[m*i+j] = m*i+j
self.count += 1

def find(self, i):
# path compression
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]

def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return

if self.rank[px] >= self.rank[py]:
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
else:
self.parent[px] = py
self.count -= 1

class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
union_find = UnionFind(grid)
n, m = len(grid), len(grid[0])

for i in range(n):
for j in range(m):
if grid[i][j] == '1':
for di, dj in DIRECTIONS:
ni, nj = i+di, j+dj
if 0 <= ni < n and 0 <= nj < m and grid[ni][nj]=='1':
union_find.union(m*i+j, m*ni+nj)

return union_find.count

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46