Count the islands

A grid of 1 for land and 0 for water. An island is land joined together up, down, left or right. Diagonals do not connect. Count the islands.

Worked example#

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

Three islands: the two by two block at the top left, the single cell in the middle, and the pair at the bottom right.

The bottom right pair is one island, not two, because the cells sit side by side. The middle cell touches nothing, so it is its own island.

The idea#

A grid is a graph. Each cell is a vertex and each cell is joined to the neighbour above, below, left and right. Counting islands is counting connected pieces, which is a walk with a visited set.

Walk the grid cell by cell. When you meet land you have not visited, that is a new island, so add one and then walk the whole island, marking every cell as visited so it is never counted again.

for each cell:
    if it is land and not visited:
        islands += 1
        flood the whole island, marking as you go

The flood can be depth first or breadth first. Either works, because the question is what is connected, not how far away it is.

Marking visited#

The simplest way is to change each visited land cell to water as you go. It needs no extra memory, and after the first pass nothing revisits it.

If the caller must not see the grid changed, keep a separate visited grid instead. Worth knowing which one the problem wants, because quietly destroying the input is a real bug in real code.

Mark a cell visited as you arrive, not when you finish with it. Otherwise the same cell is queued several times over before any of them is processed.

Watch the recursion depth#

A grid that is all land, of any size, becomes one recursion as deep as there are cells. Fifty thousand cells is a stack overflow in most languages. Breadth first with an explicit queue has no such limit.

The cost#

Time O(rows x cols): every cell is visited once. Memory O(rows x cols) in the worst case, for the stack or the queue.

Constraints#

• 1 <= rows, cols <= 300
• Every cell is 0 or 1, written as rows of digits with no spaces