Solve All Island Problems with DFS

The Island series of algorithm problems are classic high-frequency interview questions. While the basic problems are not difficult, there are some interesting extensions, such as finding the number of sub-islands, counting islands with different shapes, etc. This article aims to cover all these problems.

The core focus of the Island series problems is to traverse a 2D array using DFS/BFS algorithms.

This article will mainly explain how to efficiently solve island problems using the DFS algorithm. However, the core idea of using the BFS algorithm is exactly the same, merely requiring a conversion from DFS to BFS.

So, how do you use DFS to search in a 2D matrix? If you consider each position in the 2D matrix as a node, with the four positions above, below, left, and right as adjacent nodes, the entire matrix can be abstracted into a network-like "graph" structure.

Based on the Framework Thinking for Learning Data Structures and Algorithms, you can easily rewrite the DFS code framework for a 2D matrix by adapting the traversal framework of a binary tree:

// Binary tree traversal framework
void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

// Two-dimensional matrix traversal framework
void dfs(int[][] grid, int i, int j, boolean[][] visited) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // out of index bounds
        return;
    }
    if (visited[i][j]) {
        // already visited (i, j)
        return;
    }

    // enter the current node (i, j)
    visited[i][j] = true;

    // enter adjacent nodes (quadtree)
    // up
    dfs(grid, i - 1, j, visited);
    // down
    dfs(grid, i + 1, j, visited);
    // left
    dfs(grid, i, j - 1, visited);
    // right
    dfs(grid, i, j + 1, visited);
}

// Binary tree traversal framework
void traverse(TreeNode* root) {
    traverse(root->left);
    traverse(root->right);
}

// 2D matrix traversal framework
void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // out of index bounds
        return;
    }
    if (visited[i][j]) {
        // already visited (i, j)
        return;
    }

    // enter the current node (i, j)
    visited[i][j] = true;

    // enter adjacent nodes (quad tree)
    // up
    dfs(grid, i - 1, j, visited);
    // down
    dfs(grid, i + 1, j, visited);
    // left
    dfs(grid, i, j - 1, visited);
    // right
    dfs(grid, i, j + 1, visited);
}

# Binary tree traversal framework
def traverse(root: TreeNode):
    if not root:
        return
    traverse(root.left)
    traverse(root.right)

# 2D matrix traversal framework
def dfs(grid: List[List[int]], i: int, j: int, visited: List[List[bool]]) -> None:
    m, n = len(grid), len(grid[0])
    if i < 0 or j < 0 or i >= m or j >= n:
        # out of index boundary
        return
    if visited[i][j]:
        # already visited (i, j)
        return

    # enter the current node (i, j)
    visited[i][j] = True

    # enter the adjacent nodes (quad tree)
    # up
    dfs(grid, i - 1, j, visited)
    # down
    dfs(grid, i + 1, j, visited)
    # left
    dfs(grid, i, j - 1, visited)
    # right
    dfs(grid, i, j + 1, visited)

// Binary tree traversal framework
func traverse(root *TreeNode) {
    traverse(root.Left)
    traverse(root.Right)
}

// 2D matrix traversal framework
func dfs(grid [][]int, i, j int, visited [][]bool) {
    m, n := len(grid), len(grid[0])
    if i < 0 || j < 0 || i >= m || j >= n {
        // out of index boundary
        return
    }
    if visited[i][j] {
        // already visited (i, j)
        return
    }

    // enter the current node (i, j)
    visited[i][j] = true

    // enter the adjacent nodes (quadtree)
    // up
    dfs(grid, i - 1, j, visited)
    // down
    dfs(grid, i + 1, j, visited)
    // left
    dfs(grid, i, j - 1, visited)
    // right
    dfs(grid, i, j + 1, visited)
}

// Binary tree traversal framework
var traverse = function(root) {
    if (!root) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
};

// 2D matrix traversal framework
var dfs = function(grid, i, j, visited) {
    var m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // out of index boundary
        return;
    }
    if (visited[i][j]) {
        // already visited (i, j)
        return;
    }

    // enter current node (i, j)
    visited[i][j] = true;

    // enter adjacent nodes (quad tree)
    // up
    dfs(grid, i - 1, j, visited);
    // down
    dfs(grid, i + 1, j, visited);
    // left
    dfs(grid, i, j - 1, visited);
    // right
    dfs(grid, i, j + 1, visited);
};

Since a two-dimensional matrix is essentially a "graph," a visited boolean array is needed during traversal to prevent backtracking. If you can understand the code above, solving all island-related problems becomes straightforward.

Additionally, here's a common trick for handling two-dimensional arrays: sometimes you'll see the use of a "direction array" to handle up, down, left, and right traversals, which is similar to the code in the previous article Union-Find Algorithm Explained:

// Direction array, representing up, down, left, right respectively
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};

void dfs(int[][] grid, int i, int j, boolean[][] visited) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // out of index bounds
        return;
    }
    if (visited[i][j]) {
        // already visited (i, j)
        return;
    }

    // enter node (i, j)
    visited[i][j] = true;
    // recursively visit the nodes above, below, left and right
    for (int[] d : dirs) {
        int next_i = i + d[0];
        int next_j = j + d[1];
        dfs(grid, next_i, next_j, visited);
    }
    // leave node (i, j)
}

vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // out of index bounds
        return;
    }
    if (visited[i][j]) {
        // already visited (i, j)
        return;
    }

    // enter node (i, j)
    visited[i][j] = true;
    // recursively traverse the nodes above, below, left, and right
    for (auto &d : dirs) {
        int next_i = i + d[0];
        int next_j = j + d[1];
        dfs(grid, next_i, next_j, visited);
    }
    // leave node (i, j)
}

# Direction array, representing up, down, left, and right respectively
dirs = [[-1,0], [1,0], [0,-1], [0,1]]

def dfs(grid: List[List[int]], i: int, j: int, visited: List[List[bool]]) -> None:
    m, n = len(grid), len(grid[0])
    if i < 0 or j < 0 or i >= m or j >= n:
        # out of index boundary
        return
    if visited[i][j]:
        # already visited (i, j)
        return

    # enter node (i, j)
    visited[i][j] = True
    # recursively visit the nodes above, below, left, and right
    for d in dirs:
        next_i = i + d[0]
        next_j = j + d[1]
        dfs(grid, next_i, next_j, visited)
    # leave node (i, j)

var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func dfs(grid [][]int, i int, j int, visited [][]bool) {
    m, n := len(grid), len(grid[0])
    if i < 0 || j < 0 || i >= m || j >= n {
        // out of index bounds
        return
    }
    if visited[i][j] {
        // already visited (i, j)
        return
    }

    // enter node (i, j)
    visited[i][j] = true
    // recursively traverse the nodes above, below, left, and right
    for _, d := range dirs {
        next_i := i + d[0]
        next_j := j + d[1]
        dfs(grid, next_i, next_j, visited)
    }
    // leave node (i, j)
}

var dirs = [[-1,0], [1,0], [0,-1], [0,1]];

function dfs(grid, i, j, visited) {
    let m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // out of index bounds
        return;
    }
    if (visited[i][j]) {
        // already visited (i, j)
        return;
    }

    // enter node (i, j)
    visited[i][j] = true;
    // recursively visit nodes above, below, left, and right
    for (let d of dirs) {
        let next_i = i + d[0];
        let next_j = j + d[1];
        dfs(grid, next_i, next_j, visited);
    }
    // leave node (i, j)
}

This approach simply uses a for loop to handle traversal in all directions (up, down, left, right). You can choose the style that suits you best. Below, we will solve the problem using the above framework combined with a visual panel.