# How to Solve Island Problems Using DFS: 6 Essential Patterns

> Master island problems with DFS. Explore 6 essential patterns for counting islands, calculating areas, detecting closures, and finding unique shapes. Solve grid graph problems efficiently.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: how-to-guide
- Published: 2026-02-25

---

**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.

```java
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.

```java
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.

```java
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.

```java
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.

```java
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.

```java
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.