Given a 2-D grid of '1's (land) and '0's (water), count the number of islands (connected components of land).
Scan every cell. When you find a '1' that hasn't been visited, increment the island count and immediately flood-fill all connected land cells (DFS or BFS) so they won't be counted again. The total number of floods equals the number of islands.
How to think about it
Recognise the pattern
Any time a problem says “count connected components” or “find regions” in a grid, think DFS/BFS flood fill. The grid is just an implicit graph where each '1' cell is a node and edges go to its four neighbours. You need to find how many disconnected groups exist — that is the classic connected-components problem.
Build the approach step by step
Brute force might try to track boundaries explicitly, which is complicated. The clean approach is flood-fill:
- Iterate over every cell
(r, c). - If
grid[r][c] == '1', you’ve found a new island. Increment the counter. - Immediately DFS from
(r, c), marking every reachable land cell as visited (flip it to'0'or use avisitedset) so future scans skip it. - After the DFS returns, continue the outer scan.
Because every cell is visited at most once by the outer scan and at most once by a DFS, total work is O(m × n).
Example grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1- (0,0)=‘1’ → island 1, flood-fill kills (0,0),(0,1),(1,0),(1,1)
- (2,2)=‘1’ → island 2, flood-fill kills (2,2)
- (3,3)=‘1’ → island 3, flood-fill kills (3,3),(3,4)
- Result: 3
Complexity
- Time — O(m × n): the outer loop visits every cell once; the DFS floods each cell at most once.
- Space — O(m × n): worst-case recursion depth if the entire grid is land (one giant island, DFS snakes through every cell). An iterative BFS with an explicit queue avoids deep stacks.