LESSON 07 OF 08Number of Islands
0% learnt
NUMBER OF ISLANDS · GRID AS A GRAPH
The scan reaches unvisited land at (0,0). What should happen?
This cell cannot belong to an island counted earlier, so it starts exactly one new connected component.
RULE TO APPLYOuter scan finds a new island; one flood fill marks that whole island.
LIVE ALGORITHM STATEIncrement once, then flood-fill from (0,0).
LAND0,0
LAND0,1
WATER0,2
WATER0,3
LAND1,0
WATER1,1
WATER1,2
LAND1,3
WATER2,0
WATER2,1
LAND2,2
LAND2,3
ISLAND COUNT
0→1
LESSON 071 / 2
REAL INTERVIEW PROBLEMCount connected groups of land, not individual cells.
Given a grid of 1s (land) and 0s (water), count islands. Land connects only up, down, left, and right.
INPUT[[1,1,0,0], [1,0,0,1], [0,0,1,1]]OUTPUT2
WHAT YOU WILL DOScan every cell. Start a flood fill only on unvisited land, move only in four valid directions, and count once per flood-fill start.