Number of Islands

Count the islands in a grid of "1" (land) and "0" (water). An island is land cells joined up, down, left or right. Cells that only touch at a corner don't connect.

Scan the grid in reading order. The first land cell of an island that the scan meets starts a flood fill, which reaches every cell of that island. So each island is counted once, when the scan finds its first cell.

A flood fill keeps a queue of cells to visit and a seen set. Mark a cell seen the moment you queue it, not when you pop it. Then no cell is queued twice, even when two of its neighbors both reach it.

Later, when the scan passes a cell that's already seen, it skips it. That island is already counted.

The outer loops find islands. The while loop drains one island's queue.

from collections import deque

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or (r, c) in seen:
                continue
            islands += 1
            seen.add((r, c))
            queue = deque([(r, c)])
            while queue:
                row, col = queue.popleft()
                for nr, nc in ((row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" and (nr, nc) not in seen:
                        seen.add((nr, nc))
                        queue.append((nr, nc))
    return islands

A depth-first fill swaps the queue for a stack or recursion and counts the same islands.

Run it on the 4 × 4 grid. The scan meets (0,0) first: islands = 1. Its fill queues (1,0) and (0,1), and neither has new land beside it, so island 1 is three cells.

The scan skips (0,1) and (1,0), already seen. At (1,3) it finds fresh land: islands = 2. That fill reaches (2,3), then (2,2). Every other cell is water or already seen, so the answer is 2.

• Mark cells when you queue them. Marking on pop lets a cell be queued twice when two neighbors reach it.
• Check the bounds before you read grid[nr][nc].
• Diagonal land doesn't connect: ["101","010","101"] is 5 islands.
• All water is 0 islands, and all land is 1.
• Recursive DFS on a long, thin island can pass Python's recursion limit. The queue can't.

Union-Find reaches the same count without a flood fill. Start with every land cell in a group of its own. For each pair of neighboring land cells, merge their groups. The answer is the number of groups left.

The example has six land cells and four neighboring pairs, and every merge joins two groups, so 2 are left.

Say the grid has R rows and C columns. The scan reads each cell once. Each land cell is queued once and checks four neighbors, so the fills add O(R · C) more. Time is O(R · C).

The seen set and the queue can each hold every cell of an all-land grid, so space is O(R · C) too.