Number of Islands

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return                     # edge
        if grid[r][c] != '1':
            return                     # water
        grid[r][c] = '0'               # sink it
        for dr, dc in (1,0), (-1,0), (0,1), (0,-1):
            sink(r + dr, c + dc)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1             # new island
                sink(r, c)
    return count

Number of Islands. In a grid map, ones are land and zeros are water. Count the islands: land joined up, down, left or right.

This map has five rows and seven columns, and four islands: a big one, a hook, a single tile, and a small one at the bottom. The single tile touches the others only at its corners, and corners don't join.

Counting land tiles gives thirteen, not four. Checking every pair of tiles for a path between them works, but it's slow.

The trick: sink each island as soon as you find it. Scan the map tile by tile. Step on land, and that's a new island: add one. Then flood it, turning every connected land tile to water. The island is gone, so it's never counted again.

In code, sink stops at the edge or on water. Otherwise it turns the tile to water and calls itself on all four neighbours. That's depth first search; a queue, breadth first, works too. The main loop scans every tile; on land, it adds one and sinks.

Let's run it. The scan starts top left: land! Island one, and the flood takes five tiles. Water, then land at the top right: island two, four tiles. Two rows down, the single tile: island three. At the bottom, island four, three tiles. The rest is water.

Each tile is scanned once and sunk at most once, so the time is rows times columns. In the worst case, one huge island, the recursion goes that deep too.

Find land, count it, sink it. That's Number of Islands.