DSA Tracker

Visualize

Number of Islands

BFS over land cells — one search per connected component

time O(rows * cols)space O(rows * cols)

A grid is a graph you were handed without the arrows drawn in: every land cell is a vertex and every 4-directional land neighbour is an edge, so 'how many islands' is really 'how many connected components'. That reframing is the whole solution — scan the cells in any order, and each time you meet land nobody has claimed yet, you have found a component no earlier search could reach, so start one search and let it consume the entire island. The scan therefore starts exactly one search per island, and the answer is how many times it started. The one detail that matters is marking a cell visited when it ENTERS the queue rather than when it leaves: a cell has up to four neighbours that can all see it at once, and marking on exit lets it queue several times.

Details

Animated on: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]] — count the groups of 1s connected 4-directionally. Drawn as a graph: each land cell is a vertex at its own grid position, each land-to-land neighbour pair an edge.

Problem:Number of IslandsMedium

Pattern:Graph BFS and DFS

BFS over land cells — one search per connected component

step 1 / 12

4x5 grid, land cells only

Only the 7 land cells are vertices; the 5 edges join land cells that touch 4-directionally. Water is not drawn because it is not part of this graph, and counting islands is now just counting connected components.

Pseudocode
1FUNCTION numIslands(grid):
2  count <- 0
3  FOR EACH CELL (r, c) IN grid
4    IF grid[r][c] = 1 AND (r, c) NOT IN visited
5      count <- count + 1
6      ADD (r, c) TO visited
7      queue <- [(r, c)]
8      WHILE queue NOT EMPTY
9        (cr, cc) <- REMOVE FIRST FROM queue
10        FOR EACH NEIGHBOUR (nr, nc) OF (cr, cc)
11          IF grid[nr][nc] = 1 AND (nr, nc) NOT IN visited
12            ADD (nr, nc) TO visited
13            APPEND (nr, nc) TO queue
14  RETURN count

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. Only the 7 land cells are vertices; the 5 edges join land cells that touch 4-directionally. Water is not drawn because it is not part of this graph, and counting islands is now just counting connected components.
  2. The scan reaches land at (0,0) that no earlier search touched, so it cannot belong to any island found so far — that makes it island 1. Seed the queue with it.
  3. Pop (0,0) and claim its unvisited land neighbours (1,0), (0,1) for island 1. They are marked visited as they are QUEUED, not as they are popped — a cell has up to four neighbours that can all see it before it is ever popped, and marking on exit would let it enter the queue several times.
  4. Pop (1,0), claim (1,1), and the queue grows to 2. Anything the queue can still reach is joined to (1,0) by land, so it belongs to island 1 — the search cannot leak into another island.
  5. Pop (0,1): its neighbours are water or already claimed, so nothing new joins the queue. 1 cell still waiting.
  6. Pop (1,1): nothing new to claim and the queue is empty, so island 1 is finished at 4 cells. The outer scan resumes from where it left off.
  7. The scan reaches land at (2,2) that no earlier search touched, so it cannot belong to any island found so far — that makes it island 2. Seed the queue with it.
  8. Pop (2,2): nothing new to claim and the queue is empty, so island 2 is finished at 1 cell. The outer scan resumes from where it left off.
  9. The scan reaches land at (3,3) that no earlier search touched, so it cannot belong to any island found so far — that makes it island 3. Seed the queue with it.
  10. Pop (3,3), claim (3,4), and the queue grows to 1. Anything the queue can still reach is joined to (3,3) by land, so it belongs to island 3 — the search cannot leak into another island.
  11. Pop (3,4): nothing new to claim and the queue is empty, so island 3 is finished at 2 cells. The outer scan resumes from where it left off.
  12. The outer scan has visited every cell and started 3 searches, so the answer is 3 islands. Each vertex's badge shows the island it was claimed by.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Number of Islands in the editorAll Graph problemsBack to roadmap