Core Insight A visited structure makes each vertex’s work happen at most once.
Common Pitfall Mark a node visited when it is scheduled, not after duplicate work is queued.
Description
Count number of islands in a 2D grid.
Constraints
- Time Complexity:
O(m·n) - Space Complexity:
O(m·n)
Tags
arraydfsbfsunion-findmatrix
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a start node or component.
- Add it to the traversal frontier.
- Visit valid unseen neighbors.
- Repeat for every remaining component if needed.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
def dfs(row, col):
if row < 0 or row == rows or col < 0 or col == cols or grid[row][col] != '1':
return
grid[row][col] = '0'
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
dfs(row + dr, col + dc)
islands = 0
for row in range(rows):
for col in range(cols):
if grid[row][col] == '1':
dfs(row, col)
islands += 1
return islands