[LC] 200. Number of Islands
TechGiven an m x n
2d grid
map of '1'
s (land) and '0'
s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Approach
Simple breath first search (BFS). Nothing special. Just keep looking for non visited grid and do the BFS and check the visited.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if len(grid) == 0:
return 0
n,m = len(grid), len(grid[0])
visited = [[False]*m for _ in range(n)]
q = collections.deque()
k = 0
for i in range(n):
for j in range(m):
if grid[i][j] == "1" and not visited[i][j]:
q.append((i,j))
while q:
x,y = q.popleft()
if visited[x][y]:
continue
visited[x][y] = True
for x1,y1 in [(0,1), (0,-1), (1,0), (-1,0)]:
new_x, new_y = x+x1, y+y1
if 0 <= new_x < n and 0 <= new_y < m and grid[new_x][new_y] == "1" and not visited[new_x][new_y]:
q.append((new_x, new_y))
k += 1
return k
Time and Space Complexity: O(N*M)
Submission
Runtime: 140 ms, faster than 68.50% of Python3 online submissions for Number of Islands.Memory Usage: 15.4 MB, less than 72.58% of Python3 online submissions for Number of Islands.