Algorithms and Data Structures · Middle · Question 30 of 75
How do you count islands (connected groups of 1s) in a grid of 0s and 1s?
- ✓Correct answer: Start BFS or DFS at each unvisited 1 to mark its island
- 2Sort each row and count the runs of 1s in it
- 3Count all the 1s and divide the total by four
Explanation
Each traversal marks one connected component, so the number of traversals started is the answer. Every cell is visited a constant number of times: O(rows × cols).