Number of Islands

Difficulty: Medium Source: NeetCode

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Example 1: Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] Output: 3

Constraints:

• m == grid.length, n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'

Prerequisites

Before attempting this problem, you should be comfortable with:

• DFS / BFS on grids — visiting cells and their neighbors systematically
• Flood fill — marking all cells belonging to the same connected component
• Union-Find — an alternative way to track connected components

1. DFS (Flood Fill)

Intuition

Scan the grid left to right, top to bottom. Whenever you hit an unvisited land cell ('1'), you’ve found a new island — increment the count and immediately “sink” the entire island by running a DFS that turns all connected '1's into '0's (or a visited marker). This way, you won’t count the same island twice.

Algorithm

1. Initialize count = 0.
2. For each cell (r, c): if grid[r][c] == '1', increment count and call dfs(r, c).
3. dfs(r, c): mark grid[r][c] = '0', then recursively call dfs on each valid land neighbor.
4. Return count.

Solution

def numIslands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # sink the cell
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count


grid = [["1","1","0","0","0"],["1","1","0","0","0"],
        ["0","0","1","0","0"],["0","0","0","1","1"]]
print(numIslands(grid))  # 3

grid2 = [["1","1","1","1","0"],["1","1","0","1","0"],
         ["1","1","0","0","0"],["0","0","0","0","0"]]
print(numIslands(grid2))  # 1

Complexity

• Time: O(M * N) — each cell is visited at most once
• Space: O(M * N) worst-case recursion stack (grid full of land)

2. BFS

Intuition

Same idea as DFS — find an unvisited island cell, increment the count, then flood-fill using a queue instead of recursion. BFS avoids potential stack overflow on very large grids (Python’s recursion limit is 1000 by default).

Algorithm

1. For each unvisited land cell (r, c), increment count and enqueue (r, c).
2. While the queue is non-empty: dequeue (r, c), mark it visited, enqueue all valid land neighbors.
3. Return count.

Solution

from collections import deque

def numIslands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                queue = deque([(r, c)])
                grid[r][c] = '0'
                while queue:
                    row, col = queue.popleft()
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = row + dr, col + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'
                            queue.append((nr, nc))

    return count


grid = [["1","1","0","0","0"],["1","1","0","0","0"],
        ["0","0","1","0","0"],["0","0","0","1","1"]]
print(numIslands(grid))  # 3

Complexity

• Time: O(M * N)
• Space: O(min(M, N)) — queue size bounded by the BFS frontier width

3. Union-Find

Intuition

Model each land cell as a node in a Union-Find (disjoint set) structure. For each land cell, union it with its right and bottom neighbors if they are also land. The number of islands equals the number of distinct components (roots) among land cells at the end.

Algorithm

1. Initialize Union-Find with each land cell as its own component.
2. For each land cell, union with right and bottom neighbors if they are land.
3. Count the number of unique roots among all land cells.

Solution

def numIslands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    parent = {}
    rank = {}

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                parent[(r, c)] = (r, c)
                rank[(r, c)] = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                for dr, dc in [(1,0),(0,1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        union((r, c), (nr, nc))

    return len({find(node) for node in parent})


grid = [["1","1","0","0","0"],["1","1","0","0","0"],
        ["0","0","1","0","0"],["0","0","0","1","1"]]
print(numIslands(grid))  # 3

Complexity

• Time: O(M * N * α(M * N)) — nearly O(M * N) with path compression
• Space: O(M * N) for the parent/rank maps

Common Pitfalls

Modifying the original grid. If the grid must be preserved, use a separate visited set instead of overwriting '1' with '0'.

Stack overflow with DFS on large grids. Python’s default recursion limit is 1000. For very large grids, prefer BFS or increase the limit with sys.setrecursionlimit.

Marking cells before enqueuing (BFS). Mark the cell as visited before adding it to the queue, not when you dequeue it. Otherwise, the same cell can be enqueued multiple times before being processed.