CODING CHALLENGE · N°25

Number of Islands

Medium GraphsBFS/DFSInterview Classic

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.

EXAMPLE 1

Input grid = [[1,1,0],[0,1,0],[0,0,1]]

Output 2

the L-shape is one island; the corner cell is another

EXAMPLE 2

Input grid = [[1,0],[0,1]]

Output 2

diagonal does NOT connect

EXAMPLE 3

Input grid = [[0,0],[0,0]]

Output 0

all water

CONSTRAINTS

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.

SOLVE IT YOURSELF

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.

YOUR TASK

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).

HINTS — 4 IDEAS

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).

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Scan the grid cell by cell. When you hit an unvisited land cell, you have found a new island — increment the count and flood-fill its entire connected component (BFS or DFS over the 4 adjacent cells) marking every cell visited so it is never counted again. Continue the scan; the count of flood-fills is the number of islands.

Complexity

Time O(rows × cols) — every cell is visited once; space O(rows × cols) worst case for the stack or queue.

Common mistakes

Re-counting cells of an island you already flooded — mark cells visited as you go (or mutate them to water).
Deep recursion blowing the call stack on a large grid — prefer an iterative BFS/DFS.
Using the wrong connectivity (4-directional vs 8-directional) for the problem.

Where this shows up

This is connected-components labeling on a grid, and the same flood-fill drives image segmentation and blob detection, the paint-bucket tool, region labeling, and any “count or size the clusters” task on a graph.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA