Number of Islands: BFS vs DFS Flood Fill, and the Recursion Trap

"Number of islands" is the grid problem most people meet first, and the standard answer fits in fifteen lines. It is also where a lot of solutions pass every small test and then fall over on a large one — not because the idea is wrong, but because of how the flood is implemented.

This article covers the idea, both ways of flooding, the difference that actually matters between them, and a check against a method that does not traverse anything at all.

The problem it solves

A grid holds 1 for land and 0 for water. Land cells that touch along an edge — up, down, left or right — belong to the same island. Count the islands.

The same shape turns up whenever a bitmap has to be split into blobs: counting separate shapes in an image, grouping connected regions on a map, finding clusters of failed cells on a chip. It is a graph problem where the graph is never built — every cell is a node, and its up-to-four neighbours are the edges.

The intuition

Sweep the grid row by row. Most cells are either water or land that has already been dealt with, so the sweep passes them by. When it meets land nobody has visited, that cell must belong to a new island — if its island had been seen before, this cell would have been visited along with it. Add one to the count.

Then make sure the rest of that island can never be counted again: flood it. Visit every land cell reachable from this one and mark it. When the flood ends, the whole island is marked, and the sweep continues past it.

So the algorithm is two loops of different kinds: an outer sweep that finds islands, and an inner flood that consumes them. The count is simply the number of floods started.

The flood is ordinary graph traversal, and either traversal works:

• BFS keeps a queue. Take a cell off the front, add its unvisited land neighbours to the back. The flood spreads in rings.
• DFS keeps a stack — usually the call stack, via recursion. It follows one direction as far as it can before backing up. The flood spreads in tendrils.

Both mark exactly the same cells. For counting, the order does not matter at all. What differs is how much memory the bookkeeping needs, and where that memory lives.

Watch it run

The sweep moves cell by cell over a 4 × 5 map. When it hits fresh land the counter ticks up and a queue floods that island, marking each neighbour the moment it joins the queue. Watch the island disappear before the sweep moves on — and watch the two cells that touch only at a corner stay separate islands.

The code

Both floods, on the same map, using a separate seen record so the caller's grid is not modified:

from collections import deque

STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1))

def islands_bfs(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]   # leave the input untouched
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1 or seen[r][c]:
                continue
            count += 1                  # first cell of an island nobody counted
            seen[r][c] = True
            q = deque([(r, c)])
            while q:
                y, x = q.popleft()
                for dy, dx in STEPS:
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < rows and 0 <= nx < cols \
                            and grid[ny][nx] == 1 and not seen[ny][nx]:
                        seen[ny][nx] = True     # mark on the way IN
                        q.append((ny, nx))
    return count

def islands_dfs(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()
    def sink(y, x):
        if not (0 <= y < rows and 0 <= x < cols) or grid[y][x] != 1 or (y, x) in seen:
            return
        seen.add((y, x))
        for dy, dx in STEPS:
            sink(y + dy, x + dx)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in seen:
                count += 1
                sink(r, c)
    return count

grid = [[1, 1, 0, 0, 1],
        [1, 0, 0, 1, 1],
        [0, 0, 1, 0, 0],
        [0, 0, 1, 0, 0]]
print(islands_bfs(grid), islands_dfs(grid))          # 3 3

big = [[1] * 60 for _ in range(60)]                  # one island, 3,600 cells
print(islands_bfs(big))                              # 1
try:
    islands_dfs(big)
except RecursionError:
    print("RecursionError")                          # RecursionError

That last line is the trap. A single island of 3,600 cells is not large, but recursive DFS can go as deep as the island is big, and Python stops at a recursion depth of about 1,000 by default. BFS stores the same bookkeeping on the heap, in a deque, and does not care.

To check both against something independent, here is a method with no traversal at all: give every land cell its own label, then repeatedly let each cell adopt the smallest label among its neighbours until nothing changes. Cells in one island end up sharing a label, so the number of distinct labels is the answer.

import random, sys

def islands_relabel(grid):             # no traversal at all: spread labels until stable
    rows, cols = len(grid), len(grid[0])
    label = [[r * cols + c if grid[r][c] == 1 else None for c in range(cols)]
             for r in range(rows)]
    changed = True
    while changed:
        changed = False
        for r in range(rows):
            for c in range(cols):
                if label[r][c] is None:
                    continue
                for dy, dx in STEPS:
                    y, x = r + dy, c + dx
                    if 0 <= y < rows and 0 <= x < cols and label[y][x] is not None \
                            and label[y][x] < label[r][c]:
                        label[r][c], changed = label[y][x], True
    return len({v for row in label for v in row if v is not None})

sys.setrecursionlimit(10_000)           # small grids only, but be safe
random.seed(2)
ok = True
for _ in range(2000):
    rows, cols = random.randint(1, 8), random.randint(1, 8)
    p = random.random()
    g = [[int(random.random() < p) for _ in range(cols)] for _ in range(rows)]
    ok &= islands_bfs(g) == islands_dfs(g) == islands_relabel(g)
print(ok)                                            # True

Two thousand random grids, from almost all water to almost all land, all agreeing.

The complexity

Every cell is looked at by the sweep once and entered by a flood at most once, and each entry checks four neighbours: O(rows × cols) time. The seen record is O(rows × cols) memory; overwriting the grid instead saves that, at the price of destroying the caller's data. The queue or stack is bounded by the size of the largest island — which, for recursion, is exactly the depth problem above.

Where it goes wrong

• Recursion on large inputs. Use BFS or an explicit stack when the grid can be big. Raising the recursion limit only moves the crash, and deep native recursion can overflow the real stack.
• Marking cells when they leave the queue instead of when they join it. The count stays right, but a cell can be queued by several neighbours before it is processed. On the 60 × 60 all-land grid that version queues 7,081 cells instead of 3,600.
• Diagonals. Four directions means corner-touching cells are separate islands. If the problem says eight, add the four diagonal steps — and nothing else changes.
• Mutating input you do not own. Sinking land to 0 is a neat trick in an interview; in production code it is a surprise for the caller.
• Empty grids. len(grid[0]) fails on []; guard it if the input allows it.

When islands appear and merge over time — cells turning to land one at a time — re-flooding after each change is wasteful; that is the job of union-find.

How to say it in an interview

"Each land cell is a node with up to four neighbours. I sweep the grid; the first unvisited land cell I find starts a new island, so I count it and flood it with BFS, marking cells as they go into the queue so each is processed once. The count is the number of floods. That's O(rows × cols) time. I'd use BFS or an explicit stack rather than recursion, because one big island can blow the recursion limit."

Mentioning the recursion limit unprompted is a small thing, but it shows you have run this on more than the example.