Patterns / Number of Islands walkthrough

Number of Islands — A Worked Walkthrough

How a grid is just a graph, solved with DFS flood fill.

The problem

Given a 2-D grid of '1' (land) and '0' (water), count the number of islands. An island is a group of land cells connected horizontally or vertically (not diagonally), surrounded by water.

See the grid as a graph

Each land cell is a node, and edges connect it to its up/down/left/right land neighbors. An island is just a connected component. So the question "how many islands" becomes "how many connected components of land", and the standard tool for connected components is a traversal — DFS or BFS — plus a way to mark cells as visited.

The plan

1. Scan every cell.
2. When you hit an unvisited land cell, that is a new island, so increment the count.
3. From that cell, flood-fill all connected land, marking each visited so it is not counted again.

The solution (DFS flood fill)

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

void sink(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1')
        return;
    g[r][c] = '0';            // mark visited by sinking the land
    sink(g, r + 1, c);
    sink(g, r - 1, c);
    sink(g, r, c + 1);
    sink(g, r, c - 1);
}

Each cell is visited a constant number of times, so this is O(rows × cols) time. Marking the grid in place keeps extra space to the recursion stack, O(rows × cols) in the worst case.

A BFS alternative

If deep recursion risks a stack overflow on a very large grid, run the flood fill with an explicit queue instead: enqueue the starting cell, then repeatedly dequeue a cell and enqueue its unvisited land neighbors. Same complexity, iterative control.

Edge cases to mention

• An empty grid → 0 islands.
• All water → 0; all land → 1.
• Mutating the input — if you may not modify the grid, use a separate visited matrix.

The takeaway

Number of Islands is the gateway graph problem: recognize that a grid is a graph, then connected components fall to a simple DFS or BFS flood fill. The same approach solves Max Area of Island, Flood Fill, and Surrounded Regions. Practice it here.