The machine receives a 2D grid where 1 means land and 0 means water, and must count the number of distinct islands — connected groups of land cells where connection means sharing an edge, not a corner.
The key insight is the "sink" trick: once the machine visits a land cell, it flips it to water. That mutation both marks the cell as visited and guarantees the cell will never start a new island, so the island count is simply the number of times the traversal begins at an unvisited land cell.
The approach has three steps. First, scan every cell in the grid; whenever a cell is land, increment the island counter and start a traversal there. Second, run a DFS (or BFS) from that cell that visits all four neighbors in-bounds and flips each land cell to water. Third, continue the scan — already-flipped cells are ignored. Every cell is processed at most once, so time is O(rows × cols) and space is O(rows × cols) in the worst case when the whole grid is one island and the stack fills.
The trickiest edge case is diagonal adjacency: cells touching only at corners are separate islands, so the machine must limit neighbors to the four cardinal directions. Empty grids and all-water grids both correctly report 0.
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def sink(r, c):
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
return
grid[r][c] = '0'
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
sink(r + dr, c + dc)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
sink(r, c)
return count