class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# time O(M*N) space O(H) worst case O(N*M) for grid filled with lands
# edge case
if not grid:
return 0
cnt = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
# loop each cell to find cell == 1 , once found, "infect" all cell == 1 and cnt += 1
if grid[i][j] == '1':
self.dfs(grid,i,j)
cnt += 1
return cnt
# dfs: for cell at x,y, go 4 directions, if find neighbour cell == 1, convert them into 0; be carefull out of boundry
def dfs(self,grid,i,j):
if not (0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j] == '1'):
return
grid[i][j] = '0'
self.dfs(grid,i+1,j)
self.dfs(grid,i-1,j)
self.dfs(grid,i,j+1)
self.dfs(grid,i,j-1)
Union Find Solution
class UF:
def __init__(self,g):
r,c = len(g),len(g[0])
self.cnt = 0
self.parent = [-1] * (r*c)
for i in range(r):
for j in range(c):
if g[i][j]=='1':
self.parent[i*c+j] = i*c+j
self.cnt += 1
def find(self,i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self,x,y):
findx= self.find(x)
findy= self.find(y)
if findx != findy:
self.parent[findx] = findy
self.cnt -= 1
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
dir = [(1,0),(-1,0),(0,1),(0,-1)]
if not grid:
return 0
uf = UF(grid)
row,col = len(grid),len(grid[0])
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
for d in dir:
x = i + d[0]
y = j + d[1]
if 0<=x< row and 0<=y < col and grid[x][y] == '1':
id1 = i*col + j
id2 = x*col + y
uf.union(id1,id2)
return uf.cnt