How to Solve Island Problems Using DFS: 6 Essential Patterns

Island problems are solved by treating the 2D grid as a graph and applying a DFS flood-fill to explore connected land components, with specific variations for counting, area calculation, closure detection, and shape uniqueness.

The repository labuladong/fucking-algorithm provides a comprehensive guide to solving island problems using DFS in 高频面试系列/岛屿题目.md. These patterns apply to classic LeetCode challenges including 200 (Number of Islands), 1254 (Number of Closed Islands), 695 (Max Area of Island), 1905 (Count Sub Islands), and 694 (Number of Distinct Islands).

The Core DFS Flood-Fill Pattern

Every island solution starts with a flood-fill traversal. Treat each land cell as a node and its four orthogonal neighbors as edges. The DFS function checks boundaries, skips water cells, marks the current cell as visited (typically by sinking it to 0), and recursively explores neighbors.

void dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) return;   // boundary check
    if (grid[i][j] == 0) return;                     // water or visited
    grid[i][j] = 0;                                   // sink the land
    dfs(grid, i + 1, j);   // down
    dfs(grid, i - 1, j);   // up
    dfs(grid, i, j + 1);   // right
    dfs(grid, i, j - 1);   // left
}

This implementation appears in the “岛屿数量” section of 高频面试系列/岛屿题目.md and serves as the foundation for all subsequent variations.

Counting Islands (LeetCode 200)

To count the total number of islands, iterate through the grid with nested loops. When encountering an unvisited land cell (1), increment the counter and trigger dfs to sink the entire connected component.

int numIslands(char[][] grid) {
    int res = 0;
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                res++;
                dfs(grid, i, j);   // erase this island
            }
        }
    }
    return res;
}

Key optimization: Modifying the input grid in-place eliminates the need for a separate visited matrix, reducing space complexity from O(m·n) to O(1) auxiliary space (excluding recursion stack).

Closed Islands (LeetCode 1254)

A closed island is a region of land completely surrounded by water, meaning it does not touch the grid border. The algorithm requires two phases:

1. Sink all land cells connected to the four borders using DFS.
2. Count the remaining islands using the standard flood-fill.

int closedIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    // Sink border-connected lands
    for (int j = 0; j < n; j++) { 
        dfs(grid, 0, j); 
        dfs(grid, m - 1, j); 
    }
    for (int i = 0; i < m; i++) { 
        dfs(grid, i, 0); 
        dfs(grid, i, n - 1); 
    }

    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {   // closed island found
                res++;
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

This pattern is documented in the “封闭岛屿的数量” section of the island problems guide.

Maximum Area of Island (LeetCode 695)

Instead of counting islands, calculate the area of each component by having dfs return the size of the explored region. Track the maximum area encountered during the grid traversal.

int maxAreaOfIsland(int[][] grid) {
    int max = 0, m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                max = Math.max(max, dfs(grid, i, j));
            }
        }
    }
    return max;
}

int dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) return 0;
    grid[i][j] = 0;
    return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j)
             + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
}

The “岛屿的最大面积” section in 高频面试系列/岛屿题目.md provides this exact implementation.

Counting Sub-Islands (LeetCode 1905)

Given two grids where grid2 potentially contains islands that are subsets of grid1, first eliminate any island in grid2 that covers land where grid1 has water. The remaining islands in grid2 are guaranteed to be sub-islands.

int countSubIslands(int[][] grid1, int[][] grid2) {
    int m = grid1.length, n = grid1[0].length;
    // Remove non-sub-islands
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid1[i][j] == 0 && grid2[i][j] == 1) {
                dfs(grid2, i, j);   // sink invalid island
            }
        }
    }
    // Count remaining valid islands
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid2[i][j] == 1) {
                res++;
                dfs(grid2, i, j);
            }
        }
    }
    return res;
}

Refer to the “子岛屿数量” section for the complete reasoning behind this two-pass approach.

Distinct Islands (LeetCode 694)

To determine the number of unique island shapes, serialize the traversal path into a string, including backtrack markers. This normalization ensures that identical shapes produce identical strings regardless of their absolute grid position.

int numDistinctIslands(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Set<String> shapes = new HashSet<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                StringBuilder sb = new StringBuilder();
                dfs(grid, i, j, sb, 0);   // 0 = dummy start direction
                shapes.add(sb.toString());
            }
        }
    }
    return shapes.size();
}

void dfs(int[][] grid, int i, int j, StringBuilder sb, int dir) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) return;
    grid[i][j] = 0;
    sb.append(dir).append(',');           // record entry direction
    dfs(grid, i - 1, j, sb, 1);   // up
    dfs(grid, i + 1, j, sb, 2);   // down
    dfs(grid, i, j - 1, sb, 3);   // left
    dfs(grid, i, j + 1, sb, 4);   // right
    sb.append(-dir).append(',');          // record backtrack
}

The “不同的岛屿数量” section explains why recording both forward and backward steps is essential for canonical shape representation.

Complexity Analysis and Implementation Tips

Time Complexity: Each cell is visited at most once, resulting in O(m·n) where m and n are the grid dimensions.

Space Complexity: The recursion depth is bounded by the maximum island size, up to O(m·n) in the worst case of a filled grid, though typically O(min(m, n)) for sparse islands.

Common Pitfalls:

• Stack overflow on large grids: Switch to an explicit stack (iterative DFS) or BFS to avoid deep recursion limits.
• Mutating input data: If the original grid must be preserved, clone it first or use a separate visited boolean matrix.
• Border handling: For closed island problems, ensure you process all four borders before the main counting loop to avoid misclassifying border-touching regions.

DFS vs. BFS: While DFS provides the most compact recursive implementation for sinking islands, BFS using a queue may be safer for languages with strict recursion depth limits or when level-order traversal is required. The repository provides a BFS framework in 算法思维系列/BFS框架.md for such cases.

Summary

• Island problems treat 2D grids as graphs where land cells are nodes and adjacency represents edges.
• The flood-fill pattern sinks visited land to avoid revisiting, eliminating the need for extra visited arrays.
• Counting islands requires a double loop to initiate DFS from every unvisited land cell.
• Closed islands require pre-processing the four borders to remove ocean-connected land before counting.
• Area calculation modifies DFS to return the size of each connected component.
• Sub-islands use a filtering phase to remove candidates that overlap with water in the reference grid.
• Distinct shapes are identified by serializing traversal paths with directional markers and backtrack indicators.

Frequently Asked Questions

What is the time complexity of DFS island problems?

Each cell is visited exactly once during the flood-fill process, resulting in a time complexity of O(m·n) where m is the number of rows and n is the number of columns. The DFS itself runs in linear time relative to the number of land cells in each component.

Should I use DFS or BFS to solve island problems?

DFS is preferred for most island problems because the recursive "sink-and-count" pattern produces cleaner, more concise code, and shape serialization for distinct islands relies on the call stack structure. BFS is recommended when dealing with extremely large grids that might cause stack overflow, or when you need to find shortest paths (though this is less common in pure island counting).

How do I avoid stack overflow when solving island problems on large grids?

Replace the recursive DFS with an iterative approach using an explicit stack, or switch to BFS using a queue data structure. Both approaches keep memory usage on the heap rather than the call stack, preventing overflow errors on grids with thousands of cells.

Why do solutions often modify the input grid instead of using a visited array?

Sinking the island by setting grid[i][j] = 0 (or water) serves dual purposes: it marks the cell as visited and prevents revisiting without allocating additional memory. This reduces auxiliary space complexity from O(m·n) to O(1). If the input must remain immutable, clone the grid first or use a separate visited matrix.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}