You are given a rectangular grid as rows of '1' (land) and '0' (water). An island is a maximal group of land cells connected horizontally or vertically — diagonals do not connect. Return how many islands the grid holds.
Examples
Example 1:
Input: grid = ["11110","11010","11000","00000"]
Output: 1
Example 2:
Input: grid = ["11000","11000","00100","00011"]
Output: 3
Example 3:
Input: grid = ["1"]
Output: 1
Example 4:
Input: grid = ["10101"]
Output: 3
Constraints
1 <= rows, columns <= 300
Every row has the same length; cells are '1' or '0'.
Prerequisites
Graph traversal — DFS and BFS, and a visited set as the thing that makes both terminate. Union-find for connectivity questions; topological order for dependency ones.
How to think about it
1. Sink Each Island as You Find It Optimal
Intuition
Every unvisited land cell begins exactly one island — so scan the grid, and each time you meet one, flood its whole island as visited before moving on. The flood is what stops the same island being counted from its other cells, and whether you use DFS, BFS or union-find changes nothing about that argument.
Algorithm
1. Scan every cell. 2. Land that is not yet visited: count one island. 3. Flood-fill from it, marking all connected land visited. 4. Continue the scan.
Time & Space
Time O(rows x columns) — each cell visited a constant number of times. Space O(rows x columns) worst case for the visited set and recursion.