Problem: Number of Islands

Problem Statement

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.

Approach: Flood Fill (DFS)

We can treat the grid as an undirected graph where each '1' is a node and its horizontal/vertical neighbors are its edges.

1. Iterate: Loop through every cell in the grid.
2. Land Found: If grid[r][c] == '1', we've found a new island.
3. Traverse: Start a DFS (or BFS) from this cell to "sink" the entire island (change '1's to '0's).
4. Increment: Add 1 to our island count.

Java Implementation (DFS)

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 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') {
        return;
    }
    
    grid[r][c] = '0'; // Sink the land
    
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

Complexity Analysis

• Time Complexity: $O(M \times N)$ where $M$ is rows and $N$ is columns. We visit every cell once.
• Space Complexity: $O(M \times N)$ in the worst case for the recursion stack (all '1's).

Interview Tips

• Mention that "sinking" the land saves space by avoiding a visited set.
• Be prepared to implement this using BFS if the interviewer asks about recursion limits.
  • BFS uses a Queue and doesn't hit StackOverflow.