LeetCode Number of Islands: Grid DFS Step by Step

LeetCode 200 Number of Islands is rated Medium and is the canonical introduction to grid traversal. It tests whether you can model a 2D array as a graph, count connected components, and write a clean DFS or BFS without bugs in the bounds checks.

The Problem

You are given an m x n 2D grid of characters. '1' is land, '0' is water. An island is a maximal region of land cells connected vertically or horizontally. Return the number of islands.

Example:

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

The grid has between 1 and 300 rows and columns.

Brute Force

A naive idea: for every land cell, do a full BFS that marks reachable cells, but use a separate visited set keyed by (row, col). This works and is what most candidates write first.

def num_islands_brute(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0

    def dfs(r, c):
        if (r, c) in visited:
            return
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        visited.add((r, c))
        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' and (r, c) not in visited:
                dfs(r, c)
                count += 1
    return count

It is correct but allocates O(rows * cols) extra memory for the visited set.

Optimal Solution

Skip the visited set by mutating the grid in place: rewrite each visited '1' to '0'. Memory drops to O(rows * cols) only for the recursion stack in the worst case, and to O(rows + cols) on average.

def num_islands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[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'
        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':
                dfs(r, c)
                count += 1
    return count

The BFS variant uses a queue and is preferable on very large grids to avoid stack overflow.

from collections import deque

def num_islands_bfs(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            count += 1
            queue = deque([(r, c)])
            grid[r][c] = '0'
            while queue:
                cr, cc = queue.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))
    return count

Walk Through an Example

Using the example grid above, we scan row by row.

At (0, 0) we find '1'. Increment count to 1, run DFS. It floods (0, 0), (0, 1), (1, 0), (1, 1) and turns them all to '0'. The first island is done.

Continuing the scan, (0, 2) through (0, 4) are '0'. Row 1 is now all '0' after the flood. At (2, 2) we find '1'. Increment count to 2, DFS, but its neighbors are water. Only one cell is in this island.

Continuing, (3, 3) is '1'. Increment count to 3. DFS floods (3, 3) and (3, 4). Done.

Return 3.

Edge Cases

• Empty grid: handle not grid or not grid[0] up front and return 0.
• All water: no DFS triggered, return 0.
• All land: a single flood from (0, 0) covers the whole grid; return 1.
• Single cell: returns 1 if '1', else 0.
• Mutating input: if the interviewer says you cannot modify the grid, use the visited set version or restore the cells after counting.

Complexity Analysis

• Time: O(rows * cols). Every cell is visited at most twice, once by the outer scan and once during DFS or BFS.
• Space: O(rows * cols) worst case for DFS recursion on a grid that is all land, or for the BFS queue in the same scenario. Average space is much smaller.

For the union-find variant, time is O(rows * cols * alpha) where alpha is the inverse Ackermann function, effectively constant.

How to Explain It in an Interview

Frame the grid as an implicit graph where each land cell is a vertex and edges connect orthogonally adjacent land cells. The number of islands is the number of connected components. Any standard traversal that visits all cells in a component, marks them, and increments a counter once per component will work.

State the marking strategy explicitly. In-place mutation is the cleanest if the problem allows it; if not, use a hash set. Walk through the four directional moves and the bounds checks before writing them; that prevents off-by-one bugs.

For follow-ups, mention union-find as an alternative, which generalizes to dynamic versions of the problem like Number of Islands II (where land is added over time). DFS or BFS would force you to re-run the whole traversal after each insert; union-find updates incrementally in near-constant time.

Related Problems

• LeetCode 130 Surrounded Regions, another grid flood fill.
• LeetCode 695 Max Area of Island, where DFS returns a size.
• LeetCode 994 Rotting Oranges, BFS by time step.
• LeetCode 305 Number of Islands II, the union-find follow-up.

Wrap up

Number of Islands is the gateway problem for grid traversal. The pattern of “outer loop finds unvisited cells, inner traversal floods the component” appears everywhere. Practice both DFS and BFS until you can write either in under three minutes. Then revisit Graphs BFS and DFS to compare with general graph traversals and try Max Area of Island as a natural next step.