Free lesson · DSA Mastery - Interview Prep, End to End

Number of Islands

Hard10 min readdsagraphs

Number of Islands

Number of Islands is the canonical grid-DFS problem and the most-asked of them all: given a grid of land ('1') and water ('0'), count the number of islands, where an island is a maximal group of land cells connected 4-directionally. The technique is exactly Flood Fill applied repeatedly - scan every cell, and each time you find an unvisited land cell, flood-fill (sink) its entire island and increment a counter. Each flood fill consumes one island, so the number of flood fills is the island count. It cements the "loop over all cells, traverse each unvisited region, count the regions" pattern that defines connected-component counting on a grid. We present the DFS sink-the-island approach (canonical) and the Union-Find approach (alternative).

The insight: counting islands is counting connected components of land. Walk the grid cell by cell. When you hit a land cell that hasn't been absorbed into an island yet, you've found a new island - increment the count, then flood-fill its entire connected region of land, marking every cell so it's never counted again (the standard trick: overwrite land '1' with water '0', "sinking" the island). Cells already sunk are skipped. The total number of times you initiate a flood fill equals the number of islands, because each flood fill claims exactly one complete component.

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

Example 1:

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

Explanation: One island of connected 1s in the top-left, one isolated 1 in the bottom-right.

Example 2:

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

Explanation: All land is connected into a single island.

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	DFS sink each island, count traversals	O(m × n)	O(m × n)	Canonical
2	Union-Find on land cells	O(m × n × α)	O(m × n)	Alternative

The DFS approach scans every cell; on each unvisited land cell it increments the count and flood-fills (sinks) the whole island so it's not recounted. The number of flood fills is the island count. Union-Find unions adjacent land cells into components, then counts distinct roots - also valid, especially if the grid arrives as a stream of land additions (Number of Islands II). Both are near-linear in the grid size. DFS sinking is the standard, simplest solution.

Approach 1: DFS Sink the Island - Canonical

The Idea

Loop over all cells. When grid[r][c] == '1' (unvisited land), increment count and call sink(r, c): a DFS that turns this cell and all 4-directionally connected land into '0', marking the entire island visited. Because sinking overwrites land with water, no cell is counted twice - subsequent scans skip the sunk cells. After scanning every cell, count is the number of islands.

Logic Flowchart

graph TD
    A["count = 0"] --> B["for each cell (r,c)"]
    B --> C{"grid[r][c] == '1'? (new land)"}
    C -->|No| B
    C -->|Yes| D["count++; sink(r,c)"]
    D --> E["sink: set grid[r][c]='0', recurse into 4 land neighbors"]
    E --> B
    B --> F["return count"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows island counting by DFS sinking. Scanning every cell, each new land cell increments the count and triggers a sink that floods its whole island to water, so it is not recounted.

Code

private static final int[] DR = {-1, 1, 0, 0};
private static final int[] DC = {0, 0, -1, 1};

public static int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length, count = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1') {     // a new, unsunk island
                count++;
                sink(grid, r, c, m, n);
            }
        }
    }
    return count;
}

private static void sink(char[][] grid, int r, int c, int m, int n) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') return;
    grid[r][c] = '0';                    // sink this land cell (marks visited)
    for (int i = 0; i < 4; i++)
        sink(grid, r + DR[i], c + DC[i], m, n);
}

// Usage:
// numIslands([["1","1","0"],["1","0","0"],["0","0","1"]]) -> 2

This Java code counts islands by scanning every cell; each new land cell increments the count and triggers a recursive sink that turns the entire connected island to water, preventing recounting.

Step-by-Step Walkthrough

A frame-by-frame trace on Example 1:

graph LR
    F0["scan (0,0)='1' → count=1, sink island: (0,0),(0,1),(1,0) become '0'"]
    F1["continue scan: (0,1),(0,2),(1,0),(1,1).. all '0' now → skip"]
    F2["reach (2,2)='1' → count=2, sink: just (2,2) (isolated)"]
    F3["scan completes. return count = 2"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough counts islands: the top-left land triggers the first sink absorbing three cells, then the isolated bottom-right land triggers the second sink, giving two islands.

Result: 2.

Complexity

Time: O(m × n) - each cell visited a constant number of times. Space: O(m × n) recursion depth worst case.

Approach 2: Union-Find - Alternative

The Idea

Treat each land cell as a node. For each land cell, union it with its right and down land neighbors (covering all adjacencies without double-counting). The number of islands is the number of distinct connected-component roots among land cells. This shines when land is added incrementally (Number of Islands II) since each addition is a near-O(1) union.

Code

public static int numIslandsUF(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] parent = new int[m * n];
    int count = 0;
    for (int i = 0; i < m * n; i++) parent[i] = i;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (grid[r][c] == '1') count++;       // start: each land its own component

    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != '1') continue;
            for (int[] d : new int[][]{{0,1},{1,0}}) {     // right, down only
                int nr = r + d[0], nc = c + d[1];
                if (nr < m && nc < n && grid[nr][nc] == '1') {
                    int a = find(parent, r*n+c), b = find(parent, nr*n+nc);
                    if (a != b) { parent[a] = b; count--; }   // merge → one fewer island
                }
            }
        }
    }
    return count;
}

private static int find(int[] parent, int x) {
    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
}

// Usage: numIslandsUF([["1","1","0"],["1","0","0"],["0","0","1"]]) -> 2

This Java code counts islands with union-find: it starts with each land cell as its own component, unions adjacent land cells, decrementing the count on each merge, leaving the number of components.

Complexity

Time: O(m × n × α(m×n)) ≈ O(m × n). Space: O(m × n) for the parent array.

Complexity Comparison

Approach	Time	Space	Key Idea
DFS sink the island	O(m × n)	O(m × n)	Each flood fill consumes one island
Union-Find	O(m × n × α)	O(m × n)	Merge adjacent land; count components

The DFS sink is the standard solution: scan all cells, and each unvisited land cell starts a flood fill that sinks its whole island, so the flood-fill count equals the island count. It's Flood Fill in a loop - the connected-component-counting pattern. Union-Find is the alternative when components merge incrementally (streaming land additions), previewing the Union-Find sub-group; for a static grid, DFS sinking is simpler.

Variations & Follow-ups

Why does "count the flood fills" equal "count the islands"?

An island is a maximal connected component of land. When you scan the grid and encounter a land cell that hasn't been sunk yet, it must belong to an island you haven't counted - because if it belonged to a previously-counted island, the flood fill for that island would have sunk it already. So every unsunk land cell you find marks the discovery of a new island. You then flood-fill its entire component, sinking all of it, so none of those cells trigger another count. The result: you initiate exactly one flood fill per island, and the flood-fill count is the island count. This is the general connected-component-counting pattern: the number of times you start a fresh traversal over unvisited nodes equals the number of components. It applies identically to counting components in an explicit graph (loop over vertices, DFS each unvisited one, count the DFS launches) - the grid is just an implicit graph. Recognizing "count the components" behind "count the islands / provinces / friend groups" lets you reach for this loop-and-traverse template immediately.

Why sink the island (overwrite land with water) instead of using a visited array?

Sinking - overwriting visited land '1' with water '0' - uses the grid itself as the visited record, saving the O(m × n) visited array (the recolor-as-visited-mark trick from Flood Fill). Once a land cell is sunk to '0', the outer scan's grid[r][c] == '1' check skips it, and the sink DFS's grid[r][c] != '1' check stops at it, so it's never reprocessed. The tradeoff is that sinking destroys the input grid. If the caller needs the grid intact (or you must run multiple analyses on the original), use a separate boolean[][] visited instead and check/mark that. In interviews, ask whether mutating the input is acceptable; for Number of Islands it almost always is, and sinking is the expected, space-efficient solution. The choice is the same space-versus-input-preservation tradeoff from Matrix Traversal: sink for O(1) extra space at the cost of the input, or use a visited array to preserve the input at O(m × n) extra space.

Why does the Union-Find approach only union with the right and down neighbors?

When iterating cells in row-major order (top to bottom, left to right) and unioning each land cell with its neighbors, you only need to check the right and down neighbors - not all four. The reason: by the time you process cell (r, c), its left neighbor (r, c-1) and up neighbor (r-1, c) have already been processed, and they would have unioned with (r, c) when it was their right/down neighbor. So unioning with left and up would be redundant - those edges are already accounted for. Checking only right and down covers every adjacency exactly once across the whole scan, avoiding double-work. This is a common optimization in grid Union-Find: pick a consistent "forward" pair of directions (right + down) so each edge is considered once. With DFS sinking, by contrast, you recurse in all four directions because the traversal explores outward from each start without a global scan order to exploit. The right-and-down trick is specific to the union-during-row-major-scan structure.

When is Union-Find preferable to DFS for this problem?

For a static grid (the input is fixed, count once), DFS sinking is simpler and equally fast - it's the standard answer. Union-Find earns its keep when the problem is dynamic: Number of Islands II adds land cells one at a time and asks for the island count after each addition. With DFS you'd re-scan the whole grid after every addition (O(k × m × n) for k additions); with Union-Find, each added cell unions with its existing land neighbors in near-O(1), updating the count incrementally - O(k × α) total. Union-Find is also natural when connectivity is the recurring query (are these two cells in the same island?) or when the problem is phrased on an explicit edge list rather than a grid. The broader principle: DFS/BFS answer "what's connected right now" in one pass; Union-Find answers "what's connected as I incrementally add edges" and supports fast repeated connectivity queries. Number of Islands is the gateway - solve it with DFS, but recognize that its dynamic cousin (Islands II) is where Union-Find becomes essential, which the Union-Find sub-group develops.

What about edge cases?

All water: No land cells; count 0.
All land (Example 2): One connected component; count 1.
Single cell: Count 1 if land, 0 if water.
Diagonal-only "connection": Diagonal land cells are not connected (4-directional only); counted as separate islands.
Single row or column: Handled by bounds checks; islands are contiguous runs of land.

Common Interview Pitfalls

Not marking cells visited (or not sinking). Causes infinite recursion or recounting the same island; sink or use a visited array.
Counting diagonal neighbors as connected. Islands are 4-directional only unless stated otherwise.
Re-scanning the whole grid per island. Sink each island once during a single scan; don't restart the scan.
Destroying the grid when the caller needs it. Use a visited array if the input must be preserved.

Why This Topic Matters

Number of Islands is the canonical connected-component count on a grid: scan every cell, and each unvisited land cell starts a flood fill (sinking the whole island) that consumes one component - so the flood-fill count is the island count. It cements the loop-over-all-cells, traverse-each-unvisited-region, count-the-regions pattern (identical to counting components in an explicit graph) and the sink-as-visited-mark space trick. Its dynamic cousin motivates Union-Find later.

The next topic, Number of Distinct Islands, raises the bar: count islands that are distinct in shape, treating two islands as the same if one can be translated (not rotated or reflected) to match the other. The technique still flood-fills each island, but now records each island's shape - typically as the sequence of relative coordinates from the starting cell, or as a canonical path signature of the DFS - and counts the number of unique shapes in a set. It extends the island-counting template with the idea of capturing and canonicalizing a traversal's structure, a powerful technique for comparing connected components by form rather than mere existence.

Back to DSA Mastery - Interview Prep, End to End