Number of Islands — Grid DFS Flood Fill

Number of Islands 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

Intuition

Model 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. Scan every cell. When you hit an unvisited land cell, increment the count and flood-fill the entire component, marking each cell as visited so it is not counted again. The cleanest “visited” marker is to overwrite the '1' with '0' in place — no extra set needed.

Explanation with 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, 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.

start grid:           after island #1:      after island #2:
[1 1 0 0 0]           [0 0 0 0 0]           [0 0 0 0 0]
[1 1 0 0 0]    -->    [0 0 0 0 0]    -->    [0 0 0 0 0]
[0 0 1 0 0]           [0 0 1 0 0]           [0 0 0 0 0]
[0 0 0 1 1]           [0 0 0 1 1]           [0 0 0 1 1]

after island #3 (final):
[0 0 0 0 0]
[0 0 0 0 0]
[0 0 0 0 0]      count = 3
[0 0 0 0 0]

Code

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

public int numIslands(char[][] grid) {
    if (grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length, count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                dfs(grid, r, c, rows, cols);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int r, int c, int rows, int cols) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0';
    dfs(grid, r + 1, c, rows, cols);
    dfs(grid, r - 1, c, rows, cols);
    dfs(grid, r, c + 1, rows, cols);
    dfs(grid, r, c - 1, rows, cols);
}

void dfs(vector<vector<char>>& grid, int r, int c, int rows, int cols) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0';
    dfs(grid, r + 1, c, rows, cols);
    dfs(grid, r - 1, c, rows, cols);
    dfs(grid, r, c + 1, rows, cols);
    dfs(grid, r, c - 1, rows, cols);
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int rows = grid.size(), cols = grid[0].size(), count = 0;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == '1') { dfs(grid, r, c, rows, cols); count++; }
    return count;
}

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 (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

• Surrounded Regions, another grid flood fill.
• Max Area of Island, where DFS returns a size.
• Rotting Oranges, BFS by time step.
• 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.