Number of Islands

Number of Islands is the classic introduction to flood fill — the move that turns a grid into a graph. It is the single most reused trick for any "connected blobs on a grid" question.

1 1 0 0
1 1 0 0
0 0 1 0
0 0 1 1

The idea

Think of each land cell as a node, with an edge to each land neighbor. Then an "island" is just a connected group of land. Counting islands = counting connected groups.

Here is the trick. Scan every cell in reading order. Most cells are water, or land we have already counted — skip those. But the moment you hit a piece of land you have not seen before, you have discovered a brand-new island. Add one to the count, then flood fill: walk that entire island and mark every cell as visited so you never count it again.

How do we "mark visited"? The simplest way is to sink the land — overwrite each "1" we touch with "0". Once flooded, the whole island is water, so the rest of the scan walks right past it.

The number of times we start a flood fill is exactly the number of islands.

Walk through it

Step through the animation. The scan pointer sweeps the grid. When it lands on the first unvisited 1 at (0,0), the count jumps to 1 and a flood fill swallows the whole top-left block — watch the land cells turn to water. The scan keeps going past the now-flooded cells until it finds the next 1 at (2,2), counts a second island, and floods it too. Final answer: 2.

Pseudocode

count = 0
for each cell (r, c) in the grid:
    if grid[r][c] is land ("1"):
        count = count + 1          # found a new island
        flood_fill(r, c)           # sink this island so we never recount it
return count
 
flood_fill(r, c):
    if (r, c) is off the grid or grid[r][c] is not land:
        return                     # base case: nothing to do
    grid[r][c] = "0"               # mark visited by sinking it
    flood_fill the 4 neighbors (up, down, left, right)

The outer loop finds islands; flood_fill erases each one so it is counted exactly once.

The Python solution

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    def flood(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"
        flood(r + 1, c); flood(r - 1, c)
        flood(r, c + 1); flood(r, c - 1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                flood(r, c)
    return count

• flood(r, c) is a recursive DFS. Its first line is the base case: if the position is off the grid, or the cell is not land, we just return.
• If the cell is land, we sink it (grid[r][c] = "0") so it can never be visited again, then recurse into all four neighbors.
• The double loop walks the grid in reading order. Each time it meets a "1" (line 12), that is a new island — bump the count (line 13) and flood it (line 14).
• After flooding, every cell of that island is "0", so the loop never re-enters it.

Complexity

We touch each of the m·n cells a constant number of times, so the work is O(m·n). The space is the recursion stack: in the worst case (the whole grid is one big island) the DFS can be m·n deep, so O(m·n). Sinking the land in place means we use no separate visited grid.

When this pattern shows up

Practice