Number of Islands, in depth: one labelling pass for count, area, perimeter, shapes, closed islands, online union-find and bridges

One labelling pass to build on

Treat each land cell as a vertex and each pair of adjacent land cells as an edge. An island is a connected component, so the answer is the number of times a full scan finds an unvisited land cell and floods out from it. Every cell is visited once and examines four neighbours, so the time is O(R·C) and the extra memory is the label array plus the queue.

Rather than writing a fresh traversal for every variant, do it once and keep two things: a label grid that says which island each cell belongs to, and the list of cells per island. Almost every variant is then a few lines on top.

from collections import deque

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

def components(grid):
    """Label every 4-connected land cell; return (labels, list of cell lists)."""
    R, C = len(grid), len(grid[0])
    label = [[-1] * C for _ in range(R)]
    comps = []
    for r in range(R):
        for c in range(C):
            if grid[r][c] != 1 or label[r][c] != -1:
                continue
            k = len(comps)
            cells, q = [], deque([(r, c)])
            label[r][c] = k                      # mark on push, not on pop
            while q:
                y, x = q.popleft()
                cells.append((y, x))
                for dy, dx in DIRS:
                    ny, nx = y + dy, x + dx
                    if (0 <= ny < R and 0 <= nx < C and grid[ny][nx] == 1
                            and label[ny][nx] == -1):
                        label[ny][nx] = k
                        q.append((ny, nx))
            comps.append(cells)
    return label, comps

Two choices matter. Cells are labelled when pushed, not when popped; labelling on pop lets the same cell enter the queue several times, which is still correct for counting but inflates the queue and double-counts area. And the traversal is iterative. The recursive version reaches one call per cell on a long snake-shaped island, and on an all-land 1000 × 1000 grid that is up to a million frames, far past Python's default recursion limit of 1,000; the iterative version above labels that grid as one island without trouble.

Worked example: count, area, perimeter

Run it on the grid in the figure. The scan finds seven islands, in the order A to G, with sizes 4, 3, 1, 2, 2, 2 and 3. That single result answers the first three variants directly:

• Count: len(comps) is 7.
• Largest area: max(len(c) for c in comps) is 4, the square A.
• Perimeter: for each cell, add one for every side that faces water or the grid edge. A gives 8, B 8, C 4, the three dominoes 6 each and G 8. An equivalent formula is 4 × cells minus 2 × internal adjacencies: the square has 4 cells and 4 adjacencies, so 16 − 8 = 8.

Distinct island shapes

Two islands have the same shape if one can be moved onto the other. The question is which moves are allowed. With translation only, subtract the minimum row and column from every cell and sort; the resulting tuple is a key you can put in a set. If rotations and reflections also count as the same, generate all eight transformations (four sign combinations, each with and without swapping the axes), normalise each, and keep the smallest. Taking the minimum gives every member of an equivalence class the same representative.

def canonical(cells, rotations=False):
    """Translation-only key, or the minimum key over the 8 rotations/reflections."""
    def norm(pts):
        my = min(y for y, _ in pts); mx = min(x for _, x in pts)
        return tuple(sorted((y - my, x - mx) for y, x in pts))
    if not rotations:
        return norm(cells)
    forms = []
    for sy in (1, -1):
        for sx in (1, -1):
            forms.append(norm([(sy * y, sx * x) for y, x in cells]))
            forms.append(norm([(sx * x, sy * y) for y, x in cells]))   # transpose
    return min(forms)

distinct = len({canonical(c) for c in comps})                    # 6
distinct_any_orientation = len({canonical(c, True) for c in comps})  # 5

On the example, E and F are both horizontal dominoes, so translation gives 6 distinct shapes. With rotation allowed, the vertical domino D joins them and the answer drops to 5. A common shortcut, recording the DFS direction sequence as a string, works for translation only, and only if you also record when the traversal backtracks; without the backtrack markers, different shapes can produce the same string.

Closed islands and border floods

A closed island is one that does not touch the grid border; in a map, it is an island the outer sea cannot reach without crossing land. With the cell lists in hand, the check is one line: keep components with no cell in the first or last row or column. In the example, C and E qualify, so the answer is 2. The equivalent single-pass trick, popular because it needs no labels, is to flood every land cell connected to the border first, turning it to water, and then count what remains. The same border flood, run on water instead of land, solves "surrounded regions" and "count enclave cells". Watch the definition in any problem statement: some versions swap 0 and 1 so that land is 0, which silently inverts every comparison.

Islands that arrive one cell at a time

Now let land arrive one cell at a time and ask for the count after each arrival. Re-running the scan costs O(R·C) per query. Union-find costs nearly constant time per addition: a new cell is a new island, and each union with a neighbouring island that is not already the same set reduces the count by one.

class Online:
    """addLand one cell at a time; island count after each addition."""
    def __init__(self):
        self.parent, self.size, self.count = {}, {}, 0

    def find(self, a):
        while self.parent[a] != a:
            self.parent[a] = self.parent[self.parent[a]]   # path halving
            a = self.parent[a]
        return a

    def add(self, y, x):
        if (y, x) in self.parent:            # already land: the classic bug
            return self.count
        self.parent[(y, x)] = (y, x); self.size[(y, x)] = 1
        self.count += 1
        for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nb = (y + dy, x + dx)
            if nb in self.parent:
                a, b = self.find((y, x)), self.find(nb)
                if a != b:
                    if self.size[a] < self.size[b]:
                        a, b = b, a
                    self.parent[b] = a; self.size[a] += self.size[b]
                    self.count -= 1
        return self.count

Adding (0,0), (0,1), (1,2), (0,2), (0,2) again, (2,2) and (5,5) produces counts 1, 1, 2, 1, 1, 1, 2. The fourth addition joins two islands at once, and the fifth is a duplicate. Delete the guard and the same sequence reports 1, 1, 2, 1, 2, 2, 3: by the fifth step (0,2) has become the root of the merged island, so re-adding it resets it to a fresh singleton of size 1 and increments the count, and because its neighbours already find it as their root, no union brings the count back down. The class was checked against a full recount after every addition on 300 random grids. Deletion is the hard direction: union-find cannot split a set, so if land can also sink, process the operations offline in reverse or use the rollback techniques in union-find variants.

Making the largest island with one flip

"Flip at most one water cell to land; how big can the largest island get?" Trying every flip and re-labelling is O((R·C)²). With labels and sizes precomputed, each water cell needs only its up to four neighbouring labels: the new island's area is 1 plus the sizes of the distinct neighbouring islands. Using a set of labels matters; a water cell bordered twice by the same island must count it once. On the example, flipping (1,2) joins A (4) and C (1) for an area of 6, the best available. Remember the case where the grid has no water: the answer is then the whole grid, which the loop never visits.

The shortest bridge

Given exactly two islands, how many water cells must be flipped to connect them? Put every cell of the first island into a queue at distance 0 and run a multi-source BFS over water; the first time the search steps onto the second island, the current distance is the answer. On the grid 11000 / 10000 / 00000 / 00011 / 00001 the answer is 4. Starting from one cell of the first island instead of all of them gives the distance from that cell, not from the island, which is the usual mistake. The pattern is the same one that solves rotting oranges and distance-to-nearest problems; see multi-source BFS.

Grids that do not fit in memory

When the grid does not fit in memory (a satellite raster, a wafer map, a huge image), the labelling changes shape but not substance. The classic approach is two-pass labelling: scan row by row, give each run of land a provisional label, union labels that touch the run above, and in a second pass replace each label with its root. Only two rows of pixels and the union-find over labels need to be in memory. For parallel work, split the grid into tiles, label each tile independently, then union labels across shared tile edges; the merge step is small because only boundary cells participate. Image libraries provide this as connected-component labelling with a choice of 4- or 8-connectivity; check which one your library defaults to before comparing results, since diagonal neighbours merge islands that 4-connectivity keeps apart.

Failure modes

Trade-offs

BFS and DFS have the same asymptotics; BFS gives distances for free, iterative DFS tends to use less queue memory on wide islands. Union-find is the right tool when edges or cells arrive over time, and the wrong one when you need per-cell distances. Mutating the grid in place to mark visited cells saves memory and is fine in a throwaway solution, but production code should not destroy its input. Two-pass labelling uses tiny memory but makes everything else (shapes, bridges) harder, so use it only when the grid genuinely does not fit. For the graph-theory view of the same ideas, including directed and dynamic graphs, read connected components.

What to do next

1. Write components() from memory, iteratively, and test it on an all-land 1000 × 1000 grid.
2. Add area, perimeter and closed-island counts on top of it, and check them against the worked example: 7 islands, largest 4, closed 2.
3. Implement both shape keys and confirm 6 versus 5 on the example.
4. Build the online union-find, then fuzz it against a recount on random grids.
5. Solve flip-one-cell and shortest bridge using the labels you already have.
6. Decide 4- versus 8-connectivity explicitly in every real use, and write it down.