This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!
Question
We have to count the number of islands in Given a 2d grid map of '1's (land) and '0's (water).
An island is defined as below.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Approach
To check a 2d grid map, DFS or BFS is useful in many cases.
This question can be solved by DFS and Union Find Algorithm.
I'm gonna write about Union Find solution in this article.
In this algorithm, we can group the nodes and find the group number of some node(we can find the parent of some node).
To solve this question, if we find the '1'(land), we're gonna union the adjacent lands horizontally or vertically as much as possible.
Repeat the above process over and over again, and then finally the number of group is the answer for this question.
Solution
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
grid_y = len(grid)
grid_x = len(grid[0])
uf = UnionFind(grid)
for i in range(grid_y):
for j in range(grid_x):
if grid[i][j] == '1':
for k, l in ([1,0], [-1,0], [0,1], [0,-1]):
ny, nx = i+k, j+l
if 0<= ny < grid_y and 0 <= nx < grid_x and grid[ny][nx] == '1':
uf.union(i*grid_x+j, ny*grid_x+nx)
return uf.count
class UnionFind:
def __init__(self, grid):
y = len(grid)
x = len(grid[0])
self.parents = [0] * (y*x)
self.count = 0
for i in range(y):
for j in range(x):
if grid[i][j] == '1':
self.parents[i*x+j] = -1
self.count += 1
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x,y = y,x
self.parents[x] += self.parents[y]
self.parents[y] = x
self.count -= 1
Thank you for reading this article!
I always welcome your feedback, question, and idea.
Top comments (1)
Hi, can you please explain the time complexity also?