The Island Counter

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4

Problem

A satellite land-cover raster arrives as a grid of cells, each the string '1' for land or '0' for water. Return how many distinct islands the raster contains, where an island is a maximal group of land cells connected horizontally or vertically.

Surrounded by water, connected by land - how many separate landmasses?

Example 1

Input:

grid = [["1","1","0","0","1"],["1","0","0","0","1"],["0","0","1","0","0"],["0","0","0","1","1"]]

Output:

4

Example 2

Input:

grid = [["1","0"],["0","1"]]

Output:

2

Worked solution and explanation

What this really is

Strip the map away and this is connected-components counting: how many separate blobs of '1' are there, where 'separate' means you cannot walk between them going up, down, left or right. Everyone reaches for a loop that counts land cells, and that is the trap. The number you want is not how many '1' cells exist, it is how many TIMES you have to start a fresh walk to consume them all. Miss that and you either report the land-cell total, or worse, forget to mark where you have been and recurse forever.

The move

Step 1: Find an unseen land cell

Scan every cell. The first time you hit a '1' you have not seen before, you have found a new island. Bump the count once, right here, not once per land cell.

Step 2: Sink the whole landmass

Flood out from that cell, walking to every orthogonally adjacent '1' and flipping it to '0' as you go. Sinking the land as you visit it is what stops you from ever starting a second walk on the same island.

Step 3: Let the loop count the starts

Because step 2 consumed the entire component, the outer loop only ever triggers step 1 once per island. No land left means no more starts, so an all-water or empty grid never increments and returns 0.

The solution

DFS flood-fill for connected components
def number_of_islands(grid: list) -> int:
    if not grid:
        return 0
    rows = len(grid)
    cols = len(grid[0])
    count = 0

    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '0'
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

Two guard clauses (out of bounds, not land) end each branch before the recursion; the outer loop counts one island per fresh start.

Count the '1' cells
Returns 8 for the first example, one per land cell. It answers 'how much land' rather than 'how many islands'.
Flood-fill from each fresh start
Returns 4. Each start consumes a whole connected blob, so the number of starts is the number of islands.

Common follow-up questions