0

Flood Fill / Number of Islands

Medium

A grid is a graph where each cell touches its four neighbours. Sink each island as you walk it and count how many walks you start.

gridDFSconnected components
TimeO(rows * cols)
SpaceO(rows * cols) worst case
InputRows of 1 (land) and 0 (water)

Scan the grid. Every unvisited land cell starts a new island.

islands0
1 / 12
for each cell:
if cell is land:
islands++
dfs(cell) // sink the whole island
dfs: mark water, then recurse into 4 neighbours
Why it matters

Overwriting visited land avoids a separate visited matrix.

Practise this
Number of IslandsMSurrounded RegionsMNumber of EnclavesMRotting OrangesM
Keyboard
space play← → stepr restartctrl K search

More in Graphs

Breadth First Search
O(V + E)
Depth First Search
O(V + E)
Dijkstra Shortest Path
O(E log V)
Topological Sort (Kahn)
O(V + E)
Union-Find (DSU)
Near O(1) amortised per operation
Kruskal Minimum Spanning Tree
O(E log E)
Next visualiser
Memoisation vs Brute Force