AlgoScope

Number of Islands

Count connected components on a grid with flood fill from every unvisited land cell.

Graph traversal, pattern, intermediate
Cell 0, 0 is painted. 2 neighbours join the queue.01234012322000200110001010100
Cell 0, 0 is painted. 2 neighbours join the queue.01234012322000200110001010100

Flood Fill: Count the islands

Decision, step 3 of 18

Island 1. Pop (0, 0). 2 neighbours still land: (1, 0), (0, 1). Paint and queue them.

How flood fill works

Cost

Best
O(r * c)
Average
O(r * c)
Worst
O(r * c)
Space
O(r * c)

Taught by the same lesson

Flood Fill covers these too, in the same run.