Number of Islands
Number of Islands is a medium Graphs problem from the Blind 75. The key pattern is flood fill, and a good solution runs in O(rows · cols) time.
Problem
Count four-directionally connected components of 1 cells in a rectangular 0/1 grid.
Examples
Example 1
Input
[[1,1,0,0],[0,1,0,1],[0,0,0,1]]Output
2Example 2
Input
[[1,1,0,1],[1,0,0,1],[0,0,1,1]]Output
2Example 3
Input
[[1,0,0],[0,1,0],[0,0,1]]Output
3Approach
Scan the grid; every unvisited land cell starts a new island, and a DFS or BFS marks all land connected to it.
| Pattern | Flood fill |
|---|---|
| Time | O(rows · cols) |
| Space | O(rows · cols) |
Watch out for
Only up, down, left and right count as connected, not diagonals.