Count the islands

Question

Given a binary grid where 1 is land and 0 is water, count the islands: maximal groups of 1s connected horizontally or vertically (not diagonally). The same structure appears as "count clusters of correlated assets" in an adjacency matrix thresholded at some correlation level. Return the number of islands. Aim for O(nm).

Accepted Answer

Scan every cell. Each time you meet an unvisited land cell, you've discovered a new island: increment the count and flood-fill outward from it, marking every reachable land cell as visited so it can never start another island. The flood fill can be DFS or BFS; an explicit stack avoids Python's recursion limit on large grids (a 1000 	imes 1000 all-land grid would recurse a million deep). On the example, floods start at (0,0), (2,2), and (3,3), three islands. Time O(nm): every cell is visited a constant number of times. Space O(nm) for the visited matrix and worst-case stack. Mark cells visite…

Count the islands

Your answer

More Coding questions