Number of Islands

MediumAmazonGoogleMetaMicrosoft

Problem

Given an m×n grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Intuition — the key insight

Each time we find an unvisited '1', it's a new island. We then flood-fill (DFS/BFS) from that cell, marking all connected '1's as visited so they don't get counted again. Count how many times we trigger a flood-fill.

Approach

1. DFS flood fill

Iterate every cell. When you find a '1', increment count and DFS in all 4 directions, marking each visited cell as '0' (or use a visited set). The DFS 'consumes' the entire island.

2. Boundary check

In DFS, return immediately if out of bounds OR cell is '0' OR already visited.

Complexity

Time

O(m × n)

Space

O(m × n)

Every cell is visited at most once. DFS recursion stack is O(m×n) in the worst case (one giant island).

Solution code

Python

def numIslands(self, grid: List[List[str]]) -> int:
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        
        grid[r][c] = '0'  # mark visited
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    
    return count

Edge cases to remember

⚠Empty grid: return 0

⚠All water: return 0

⚠All land: return 1 (one giant island)

⚠Modifying grid: if read-only, use a visited boolean matrix instead

Hints

What pattern do you think this problem uses?