Number of Islands at Microsoft — Interview Guide

• Each unvisited land cell starts a new island; flood-fill it to mark visited cells.
• DFS is simplest but can blow the recursion stack on large grids — switch to BFS or iterative DFS.
• Union-find works too and generalizes to dynamic connectivity.

1. Iterate every cell; when you find unvisited land, increment the count and run DFS/BFS to mark the whole island.
2. Mark cells in-place (set to '0') or with a visited set to avoid revisiting.

def num_islands(grid):
    if not grid: return 0
    rows, cols, count = len(grid), len(grid[0]), 0
    def dfs(r, c):
        if 0 <= r < rows and 0 <= c < cols and grid[r][c] == '1':
            grid[r][c] = '0'
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                dfs(r+dr, c+dc)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count