### Number of Islands

Graph
Medium

Approach

Diagrams

Analysis

Time

O(mn)

Space

O(mn)
``````from collections import deque

class Solution:
def numIslands(self, grid):
numRows, numCols = len(grid), len(grid[0])
count = 0

visited = [[False for col in range(numCols)] for row in range(numRows)]

for row in range(numRows):
for col in range(numCols):
if grid[row][col] == '0' or visited[row][col]:
continue

start = (row, col)
self.bfs(start, visited, grid, numRows, numCols)
count += 1

return count

def bfs(self, start, visited, grid, numRows, numCols):
queue = deque([start])

row, col = start
visited[row][col] = True

while queue:
node = queue.popleft()
neighbors = self.getNeighbors(node, numRows, numCols)

for neighbor in neighbors:
row, col = neighbor

if grid[row][col] == '0' or visited[row][col]:
continue

queue.append(neighbor)
visited[row][col] = True

def getNeighbors(self, coord, numRows, numCols):
row, col = coord
neighbors = []

deltaRow = [-1, 0, 1, 0]
deltaCol = [0, 1, 0, -1]

for delta in range(len(deltaRow)):
neighborRow = row + deltaRow[delta]
neighborCol = col + deltaCol[delta]

isValid = 0 <= neighborRow < numRows and 0 <= neighborCol < numCols

if isValid:
neighbors.append((neighborRow, neighborCol))

return neighbors``````

Learn