DSA Number of Islands

The problem

A grid is a table of cells in rows and columns. Each cell holds 1 for land or 0 for water. An island is a patch of land cells joined through side neighbours, meaning the cells above, below, left and right.

Cells that touch only at a corner are not joined. The question asks how many islands the grid holds. The code below prints three grids as rows and states the count each one must give.

grids = [
    ["11000", "11000", "00100", "00011"],
    ["101", "010", "101"],
    ["111", "101", "111"],
]
expected = [3, 5, 1]
for grid, exp in zip(grids, expected):
    for row in grid:
        print(row)
    print("expected islands:", exp)
    print()

The first grid holds a block of four, a single cell, and a pair, so it counts three. The second grid holds five single cells, because its land touches only at corners. The third grid is one ring of land around a water cell, so it counts once.

Intuition

The first idea counts land cells. A grid with seven land cells looks like it might hold seven of something. That count answers a different question, because joined cells form one island, not several.

The block in the first grid makes the gap plain. Four land cells sit side by side and form a single island. Counting cells gives 7 for the whole grid, while counting regions gives 3.

grid = ["11000", "11000", "00100", "00011"]
land = 0
for row in grid:
    for cell in row:
        if cell == "1":
            land += 1
print("land cells:", land)
print("islands: 3")
print("the top-left block alone: 4 cells, 1 island")

Cells and regions only agree when every island holds one cell. The right unit is the region. A correct count starts something once per region and never again inside the same region.

Brute force

A clumsy route gives every land cell its own label and then merges labels. Scan the grid again and again. Whenever two side neighbours hold different labels, replace the larger label with the smaller one everywhere. Stop when a full scan changes nothing, then count the labels that remain.

The route is correct. It is slow because each scan rewalks the whole grid, and the merges can need many scans to travel across a wide island. The counter below bills every scan.

def brute_islands(grid):
    if not grid:
        return 0, 0
    rows, cols = len(grid), len(grid[0])
    labels = [[0] * cols for _ in range(rows)]
    nxt = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                nxt += 1
                labels[r][c] = nxt
    scans = 0
    changed = True
    while changed:
        changed = False
        scans += 1
        for r in range(rows):
            for c in range(cols):
                if labels[r][c] == 0:
                    continue
                for dr, dc in [(1, 0), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and labels[nr][nc] != 0:
                        if labels[nr][nc] != labels[r][c]:
                            hi = max(labels[nr][nc], labels[r][c])
                            lo = min(labels[nr][nc], labels[r][c])
                            for rr in range(rows):
                                for cc in range(cols):
                                    if labels[rr][cc] == hi:
                                        labels[rr][cc] = lo
                            changed = True
    found = set()
    for r in range(rows):
        for c in range(cols):
            if labels[r][c] != 0:
                found.add(labels[r][c])
    return len(found), scans

grid = ["11000", "11000", "00100", "00011"]
count, scans = brute_islands(grid)
print("islands:", count)
print("full-grid scans:", scans)

The count is right and the scan bill is already visible on a four-row grid. A flood does the same joining in one pass per island, with no repeated whole-grid scans.

The optimal solution: flood each island once

The key idea is one sentence. Scan the grid once, and whenever an unseen land cell appears, count one island and flood from it to mark its whole region as seen.

A flood is a search that spreads to side neighbours. It marks each land cell it reaches, so no cell of that island can start a second count. Water and seen cells stop the spread.

def count_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    def flood(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == "0" or (r, c) in seen:
            return
        seen.add((r, c))
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)
    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
                flood(r, c)
    return count

grids = [
    ["11000", "11000", "00100", "00011"],
    ["101", "010", "101"],
    ["111", "101", "111"],
]
for grid in grids:
    print("islands:", count_islands(grid))

All three cases from the first section pass. A breadth-first flood with a queue gives the same counts. The two searches differ in visit order, not in which cells belong to an island.

Walkthrough

Follow the flood count on the first grid. The scan moves row by row. The trace prints the count and the seen cells each time a flood finishes.

grid = ["11000", "11000", "00100", "00011"]
rows, cols = len(grid), len(grid[0])
seen = set()

def flood(r, c):
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    if grid[r][c] == "0" or (r, c) in seen:
        return
    seen.add((r, c))
    flood(r + 1, c)
    flood(r - 1, c)
    flood(r, c + 1)
    flood(r, c - 1)

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
            flood(r, c)
            print("after flood", count, "from", (r, c), "seen:", len(seen))
print("total islands:", count)

The first flood starts at the top-left cell and marks the four cells of the block. The scan then skips every seen cell until it reaches the single cell in row three, which floods alone. The last flood covers the pair in the bottom row, and the count ends at three.

Complexity

Time is O(rows x cols). Each cell is scanned once by the outer loops and marked at most once by a flood, so the total work grows with the number of cells.

Space is O(rows x cols) in the worst case. The seen set can hold every land cell, and one flood on a grid of pure land also stacks one call per cell along its path.

def counted(grid):
    if not grid:
        return 0, 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    def flood(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == "0" or (r, c) in seen:
            return
        seen.add((r, c))
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)
    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
                flood(r, c)
    return count, len(seen)

for size in [2, 4, 8]:
    grid = ["1" * size for _ in range(size)]
    count, marked = counted(grid)
    print("grid", size, "x", size, "cells:", size * size, "islands:", count, "cells marked:", marked)

The marked count equals the cell count at every size. One island of pure land still needs every cell marked once. Doubling the side multiplies the cells by four, and the marked count follows exactly.

Edge cases and pitfalls

An empty grid holds no islands. A grid of pure water also holds none, because no flood ever starts. A grid of pure land holds exactly one, however large it is.

Diagonal contact is the classic pitfall. Two cells touching at a corner look joined on paper and stay separate under the side-neighbour rule. Adding diagonal steps to the flood silently merges them and undercounts.

def count_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    def flood(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == "0" or (r, c) in seen:
            return
        seen.add((r, c))
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)
    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
                flood(r, c)
    return count

print("empty grid:", count_islands([]))
print("all water:", count_islands(["000", "000"]))
print("single land cell:", count_islands(["1"]))
print("single water cell:", count_islands(["0"]))
print("diagonal pair:", count_islands(["10", "01"]))
print("all land 3x3:", count_islands(["111", "111", "111"]))

The diagonal pair answers two, not one. That single line is the side-neighbour rule in action. Every other line follows from the scan rule alone, with no special cases in the code.