# [LC] 200. Number of Islands

Given 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)
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.