Number of Islands (LeetCode 200)

The problem

You get a 2-D grid of '1' (land) and '0' (water). An island is a group of land cells connected up, down, left or right; diagonals don’t count. Return how many islands there are.

Input:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: 3

The top-left 2×2 block is one island, the single 1 in the middle is another, and the pair at the bottom right is the third.

How to think about it

Start with brute force. You could, for every land cell, work out which island it belongs to by comparing it with every other land cell. That gets messy and slow fast, and it hides the real structure.

The key insight: the grid is a graph. Each cell is a node. Each land cell has an edge to its land neighbours above, below, left and right. An island is just a connected component of that graph. So the question becomes “how many connected components are there?”, and that has a standard answer.

Count components by flooding them. Scan the grid. The first time you step on a land cell you haven’t seen, you’ve found a new island, so add one. Then flood that entire island (visit every connected land cell) so none of its cells get counted again. Keep scanning. Every flood you start is exactly one island.

Which pattern is this? Graph traversal: DFS (or BFS) flood fill. The tell is “connected regions in a grid”.

Approach

1. Walk every cell row by row.
2. When you hit a '1', add one to count and call dfs from it.
3. dfs(r, c) stops if (r, c) is off the grid or not land. Otherwise it marks the cell as '0' (sinking it so it’s never counted again) and recurses into its four neighbours.
4. When the scan ends, count is the number of islands.

Sinking the land in place means you don’t need a separate visited set. If you’re not allowed to change the input, use a visited set instead; the logic is identical.

Solution

def num_islands(grid):
    if not grid: return 0
    R, C = len(grid), len(grid[0]); count = 0
    def dfs(r, c):
        if r < 0 or c < 0 or r >= R or c >= C or grid[r][c] != '1': return
        grid[r][c] = '0'                      # sink it: never count it again
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1': count += 1; dfs(r, c)   # new island found
    return count
# num_islands([["1","1","0","0","0"],["1","1","0","0","0"],
#              ["0","0","1","0","0"],["0","0","0","1","1"]]) -> 3

Dry run

On the example grid above (rows and columns are 0-indexed):

Three floods are started, so the answer is 3.

Complexity

• Time: O(R·C). The scan visits each cell once, and each land cell is sunk exactly once. After that, every later visit returns immediately.
• Space: O(R·C) in the worst case. This is the recursion depth: if the whole grid is land, a single flood can go R·C calls deep. A BFS with a queue has the same worst case. For very large grids, use an explicit stack or BFS to avoid Python’s recursion limit.

Edge cases and pitfalls

• Empty grid returns 0 (handled by the first line).
• All water returns 0; all land returns 1.
• Diagonals don’t connect. Only check the four directions. Adding diagonals is a different problem.
• Forgetting to mark visited sends the flood fill into infinite recursion, bouncing between two neighbours.
• Recursion depth. A 1000×1000 grid of land will blow Python’s default recursion limit. Mention the iterative version in an interview.

Related problems

• Max Area of Island (LeetCode 695): the same flood fill, but return the size of each island.
• Surrounded Regions (LeetCode 130): flood fill from the border instead.
• Pacific Atlantic Water Flow (LeetCode 417): two flood fills, then intersect.