Mid-levelMid (3–6 yrs)CodingPythonAmazonGoogleBloomberg
Number of Islands
Given an m×n grid of '1' (land) and '0' (water), return the number of islands. An island is land connected 4-directionally.
Answers use simple, clear English.
Audio N/ATime: O(m*n)Space: O(m*n) worst-case recursion
Quick interview answer
Scan the grid; on each unvisited '1', increment count and DFS/BFS flood-fill marking visited land as water or via a visited set.
Detailed answer
Scan the grid; on each unvisited '1', increment count and DFS/BFS flood-fill marking visited land as water or via a visited set. Union-Find also works and interviews sometimes ask for it on large grids.
Full explanation
Union-Find also works and interviews sometimes ask for it on large grids.
Real example & use case
Satellite land-cover tool counting contiguous farmland parcels.
Pros & cons
Pros: DFS flood-fill is intuitive. Cons: recursion depth on huge islands — prefer iterative BFS.
Code example
def num_islands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0'
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
dfs(r + dr, c + dc)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return countPractice code · python (view only · no execution)
def num_islands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0'
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
dfs(r + dr, c + dc)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count#dfs#bfs#grid