Number of Islands

Signal

"Count connected groups in a grid" is a flood-fill counting problem: every time you find an unvisited land cell, it's the start of a brand-new island — flood fill it to mark the whole group visited, then keep scanning.

Approach

Scan every cell. When you hit a '1' that hasn't been visited yet, increment the island count and flood fill outward (DFS or BFS) marking every connected land cell as visited so it's never counted again. Cells that are water or already visited are simply skipped during the scan.

Skeleton

count = 0
for each cell:
    if cell is land and not visited:
        count += 1
        flood_fill(cell)  # mark this whole connected group visited
return count

Solution

def num_islands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()

    def flood_fill(r: int, c: int) -> None:
        stack = [(r, c)]
        visited.add((r, c))
        while stack:
            cr, cc = stack.pop()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = cr + dr, cc + dc
                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and (nr, nc) not in visited
                    and grid[nr][nc] == '1'
                ):
                    visited.add((nr, nc))
                    stack.append((nr, nc))

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                count += 1
                visited.add((r, c))
                flood_fill(r, c)
    return count

Complexity

O(rows · cols) time — every cell is visited at most once. O(rows · cols) space for the visited set (or the recursion stack if you use recursive DFS instead).

Pitfalls

• Mutating the input grid in place (writing '0' over visited land) works and saves the visited set's space, but changes data the interviewer handed you — ask before doing it, or default to a separate visited set.
• Recursive DFS on a large grid can hit Python's recursion limit; an explicit stack (as above) or BFS with a queue sidesteps that.
• Forgetting to mark a cell visited the moment it's pushed (not when it's popped) lets the same cell get queued multiple times before it's processed.