# [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.