Number of Islands
The canonical connected-components question — asked at every company that has ever run an interview. Flood-fill each unvisited patch of land, count how many times you had to start a flood. Grid traversal, visited bookkeeping, no tricks.
The problem
Given grid, a 2D list of 0s (water) and 1s (land), return the number of islands — groups of 1s connected horizontally or vertically (not diagonally). Traverse each island once with BFS or DFS, marking cells visited so no island is counted twice.
grid = [[1,1,0],[0,1,0],[0,0,1]]2grid = [[1,0],[0,1]]2grid = [[0,0],[0,0]]0- Connectivity is 4-directional (up, down, left, right).
- Do not count an island more than once — mark visited cells.
- The grid may be empty; return 0.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.
Implement num_islands(grid) → the count of 4-connected groups of 1s, using BFS or DFS with a visited set (or by sinking visited land in a copy).
- Scan every cell; when you find an unvisited 1, increment the count and flood from it.
- Flood with an explicit stack or queue: pop a cell, push its 4 unvisited land neighbours.
- Mutating a copy of the grid (set visited land to 0) is the simplest visited set.
- Bounds-check before you look: r in [0, rows), c in [0, cols).
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.