LeetCode Study Note | Problem 200: Number of Islands

🌊 Problem Summary

You are given a 2D grid consisting of '1's (land) and '0's (water).

An island is formed by connecting adjacent lands horizontally or vertically.

Return the number of islands.

🧠 Core Idea: DFS on a Grid

This is a classic grid DFS problem, which is essentially a simplified graph traversal problem in disguise.

Key Observations:

• Each cell has 4 neighbors: up, down, left, right.

• Start DFS whenever you encounter a '1' that hasn’t been visited.

• Use DFS to “sink” the entire island (by marking visited cells).

• Count how many times DFS is triggered — this equals the number of islands.

🧱 Grid DFS Template

Grid DFS is similar to binary tree DFS, but slightly more complex because each node (cell) can have up to 4 neighbors.

DFS Recursion Structure:

void dfs(char[][] grid, int r, int c) {
    if (!inArea(grid, r, c)) return;
    if (grid[r][c] != '1') return;

    // Mark current cell as visited
    grid[r][c] = '0';  // Optional: can use other markers like '2'

    // Visit all four directions
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

boolean inArea(char[][] grid, int r, int c) {
    return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}

✅ Full Solution (Java)

class Solution {
    public 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++;
                    dfs(grid, r, c);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
        if (grid[r][c] != '1') return;

        grid[r][c] = '0'; // Mark as visited

        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
}

🧠 Summary of Key Techniques

⚠️ Tips and Pitfalls

• Use of '0' to mark visited: convenient but may be risky in more complex variations (consider using a visited array or other marker like '2').

• Off-by-one errors: make sure your loop bounds are i < grid.length, not i < grid.length - 1!

• Recursive Stack Overflow: On very large grids, Java might hit recursion limit. Use BFS with queue to avoid it if needed.