BFS · 200 Number of Islands

Count the islands

You're given a grid of land (1) and water (0). An island is a clump of land connected up/down/left/right. Count how many separate islands there are.

The BFS idea → Walk the grid cell by cell. The first time you step onto land you haven't seen, that's a new island: count it, then run BFS from there to "flood" the entire connected blob so you never count it again. The queue holds the cells whose neighbours you still need to explore. BFS spreads outward like spilled water.

Grid

land (unseen) water in queue (frontier) current flooded island

What's happening

Queue (FIFO →)

Counters

Code

speed

Complexity: O(rows × cols) time, O(rows × cols) space (visited + queue). Each cell is enqueued and dequeued at most once. · Same idea solves: Max Area of Island (695), Flood Fill (733).