Count Islands (Connected Components)

Difficulty: Medium · Pattern: Graph DFS · Concept: General Coding (DSA) — Core Patterns to Drill

Given a 2D grid of 1s (land) and 0s (water), count the number of islands — groups of 1s connected horizontally or vertically (not diagonally). This is a grid dressed up as a graph problem: each land cell is a node, each cell is implicitly connected to its up/down/left/right neighbors, and an "island" is exactly a connected component.

Your task: implement count_islands(grid), using DFS (or BFS — either correctly solves this) to explore each island fully before moving to the next, without recounting cells or mutating the input grid.

Implement it yourself

assert count_islands([[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]) == 3
assert count_islands([[1, 1, 1], [1, 1, 1], [1, 1, 1]]) == 1
assert count_islands([[0, 0], [0, 0]]) == 0
assert count_islands([[1, 0, 1], [0, 0, 0], [1, 0, 1]]) == 4
assert count_islands([[1]]) == 1

Next: Detect a Cycle in a Directed Graph