Description
Count connected groups of '1' cells in a rectangular grid. Connectivity is orthogonal. This solution changes visited land to water.
Solution
def num_islands(grid):
rows, cols, count = len(grid), len(grid[0]), 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1':
continue
count += 1
grid[r][c] = '0'
stack = [(r,c)]
while stack:
x,y = stack.pop()
for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
nx,ny = x+dx,y+dy
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
grid[nx][ny] = '0'
stack.append((nx,ny))
return countExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[["1","0"],["0","1"]]]- Output
2
Diagonal cells are not connected.
Example 2
- Input
[[["1","1"],["1","1"]]]- Output
1
Every land cell belongs to the same component.
Example 3
- Input
[[["0"]]]- Output
0
There is no land.
Approach
Flood-fill each unseen land cell and count one island per new fill.
Time & space
O(R C) time; O(R C) stack space. V is the vertex count, E the edge count; R and C denote grid dimensions when used.