Grid Traversal Example: Counting the Islands on a Map

Scan every square, and each time the scan finds land no fill has reached, count an island and fill all the land joined to it.

Counting the separate regions of a grid takes a scan over every cell and a flood fill from each cell the fills have not yet reached: the count is the number of fills started. A flood fill marks every cell joined to a starting cell, the way a paint bucket colours a whole area in a drawing program. On the map below, L is land and . is water, and two land squares belong to the same island when they touch above, below, left or right.

text

L L . . L
L . . L .
. . L . .
L . . . L
L L . L L

How many islands does the map hold?

Three are single squares on a diagonal, at (0, 4), (1, 3) and (2, 2), and each is its own island because squares that touch only at a corner are not joined. Joining corner neighbours too would give 4.

The scan goes row by row. Each land square it meets that no fill has reached starts a new island, and the fill from it labels every land square it can reach. Later scan steps pass over those squares, so each island is counted once. The fill uses a stack of its own rather than recursion, because a recursive fill can go one call deep per square: a 100 by 100 map of land would need 10,000 calls, far past Python's default limit of 1,000. The listing prints the map with each land square labelled by the island that filled it.

islands.pypy

DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))


def label_islands(grid: list[str]) -> list[list[str]]:
    rows, cols = len(grid), len(grid[0])
    label = [["." for _ in range(cols)] for _ in range(rows)]
    islands = 0
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == "L" and label[row][col] == ".":
                name = chr(ord("A") + islands)
                islands += 1
                label[row][col] = name
                stack = [(row, col)]
                while stack:
                    cell_row, cell_col = stack.pop()
                    for d_row, d_col in DIRECTIONS:
                        r, c = cell_row + d_row, cell_col + d_col
                        if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "L" and label[r][c] == ".":
                            label[r][c] = name
                            stack.append((r, c))
    return label


world = ["LL..L", "L..L.", "..L..", "L...L", "LL.LL"]
label = label_islands(world)
for line in label:
    print(" ".join(line))
print("islands:", len({name for line in label for name in line if name != "."}))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

A A . . B
A . . C .
. . D . .
E . . . F
E E . F F
islands: 6

The labels show the order the scan met the islands: A at the top left, B to D along the diagonal, then E and F on the bottom rows. Every square is scanned once and filled at most once, and each fill looks at four neighbours, so the count is O(R · C) time, with O(R · C) space for the labels and the stack. Which neighbours count as joined is part of the question, and the answer changes with it.

← → move through sections and cards