200 - Number of Islands

Difficulty: Medium | Pattern: Graph DFS / BFS / Union-Find | Company tags: Amazon, Google, Facebook, Microsoft, Bloomberg

Problem Statement

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 all surrounded by water.

Example 1:

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

Example 2:

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

Approach 1: DFS — Sink the Island

Key insight: When we find a '1', increment the island count and do a DFS to "sink" all connected land cells (mark them as '0') so we don't count them again.

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        # Out of bounds or water → stop
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # sink: 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

Note: This modifies the input grid. If that's not allowed, use a separate visited set instead.

Approach 2: BFS

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'  # mark before enqueuing
                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':
                            queue.append((nr, nc))
                            grid[nr][nc] = '0'  # mark when enqueuing to avoid duplicates
    
    return count

Algorithm Flow

Dry Run (Example 2)

Grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

• (0,0): '1' → count=1, DFS sinks (0,0),(0,1),(1,0),(1,1)
• (2,2): '1' → count=2, DFS sinks (2,2)
• (3,3): '1' → count=3, DFS sinks (3,3),(3,4)

Result: 3 ✓

Without Modifying Input: Use Visited Set

def numIslands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0
    
    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == '0' or (r, c) in visited):
            return
        visited.add((r, c))
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            dfs(r+dr, c+dc)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                count += 1
                dfs(r, c)
    
    return count

Complexity

Approach	Time	Space
DFS (sink)	O(m × n)	O(m × n) worst case call stack
BFS	O(m × n)	O(min(m, n)) queue
DFS (visited set)	O(m × n)	O(m × n) for visited set

Key Terms

Term	Definition (in context of this problem)
DFS/BFS traversal	Explores every cell connected to a land cell via 4-directional adjacency to identify one island fully.
Visited/sunk marker	Flips a '1' to '0' (or records it in a visited set) so the same land cell is never counted twice.
Connected component	An island is exactly one connected component of '1' cells under horizontal/vertical adjacency.
Flood fill	The general technique (used here) of spreading outward from a seed cell until boundaries (water/edges) are hit.
Union-Find (alternative)	Merges adjacent land cells into the same set; island count = number of distinct sets, useful for dynamic/streaming grids.

FAQ

1. Can this be solved without extra space? Yes, by mutating the input grid in place (sinking '1's to '0's) as shown in Approach 1/2, giving O(1) auxiliary space aside from the recursion/queue. If the grid must stay unmodified, use the visited set version at the cost of O(m×n) extra space.
2. What if the grid is empty or has no land? numIslands should return 0. The code handles this via the if not grid: return 0 check and the fact that the loop simply never finds a '1'.
3. How does using diagonal adjacency change the answer? Allowing 8-directional connectivity (adding diagonals) can merge islands that were previously separate, so the count would typically decrease or stay the same, never increase.
4. What's the common follow-up interviewers ask? "Count islands in a 3D grid" or "return the size of the largest island" (LeetCode 695), both solved with the same DFS/BFS template plus a size counter. Another common follow-up is handling streaming land additions efficiently, which motivates Union-Find (LeetCode 305).
5. Why can DFS recursion be risky here, and how do you fix it? For very large grids (e.g., 1000×1000 all land), recursive DFS can hit Python's recursion limit or stack overflow; converting to iterative DFS with an explicit stack, or using BFS with a queue, avoids this risk.

Quick Revision

• Problem: count connected components of '1' cells in a grid using 4-directional adjacency.
• Two viable traversals: DFS (recursive, sinks cells) or BFS (queue-based, sinks cells before enqueueing).
• Increment count only when you encounter an unvisited '1'; then flood-fill to mark the whole island visited.
• Sinking the grid in place avoids a separate visited structure but destroys the input — use a visited set if that's not allowed.
• Every cell is visited at most once, giving O(m × n) time regardless of DFS or BFS.
• DFS space is bounded by the call stack (worst case O(m×n) for an all-land grid); BFS space is bounded by the queue (O(min(m,n)) for typical shapes).
• Boundary checks (0 <= r < rows, 0 <= c < cols) must be evaluated before indexing to avoid out-of-bounds errors.
• Union-Find is the go-to alternative when islands need to be merged incrementally (e.g., land added over time).

Related Problems

• 695-MaxAreaOfIsland — same traversal, but track island size instead of just counting islands.
• 694-NumberOfDistinctIslands — extends this pattern to distinguish islands by shape.
• 733-FloodFill — the core flood-fill technique applied directly.
• 417-PacificAtlanticWaterFlow — multi-source grid DFS/BFS variant.
• LeetCode 305 (Number of Islands II) — dynamic version solved with Union-Find; not in this directory but same pattern family.