Number of Islands
FreeGraphsMedium42 of 75
The problem
Count connected groups of land in a rectangular grid of 0s and 1s. Land connects horizontally or vertically, never diagonally.
Example
[[1, 0, 1], [1, 0, 0], [0, 1, 1]] → 3
Need a hint?
Each unseen land cell begins one component.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Scan the grid. When a cell is land and unvisited, increase the answer and flood-fill all land reachable from it using a stack or queue. Mark cells when enqueuing to prevent repeated work. Keep a visited set if the input must remain unchanged.
Complexity
O(mn) time and O(mn) worst-case space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.