Pattern visualizer
Number of Islands
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. 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..
BFS over land cells — one search per connected component
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.
1FUNCTION numIslands(grid):2 count <- 03 FOR EACH CELL (r, c) IN grid4 IF grid[r][c] = 1 AND (r, c) NOT IN visited5 count <- count + 16 ADD (r, c) TO visited7 queue <- [(r, c)]8 WHILE queue NOT EMPTY9 (cr, cc) <- REMOVE FIRST FROM queue10 FOR EACH NEIGHBOUR (nr, nc) OF (cr, cc)11 IF grid[nr][nc] = 1 AND (nr, nc) NOT IN visited12 ADD (nr, nc) TO visited13 APPEND (nr, nc) TO queue14 RETURN count
← / → step · space play · Home restart