Number of Islands (LC 200)

Pattern: DFS / BFS Flood Fill on a 2-D Grid Difficulty: Medium Key Concept: Iterate every cell. When you hit unvisited '1', run DFS/BFS to “sink” all connected '1's into '0's and increment a counter.

Problem Statement

Given a 2-D grid char[][] grid of '1' (land) and '0' (water), return the number of islands. An island is a maximal group of '1's connected horizontally/vertically (NOT diagonally).

Example

grid =
[['1','1','1','1','0'],
 ['1','1','0','1','0'],
 ['1','1','0','0','0'],
 ['0','0','0','0','0']]
→ 1

1. Algorithm & Pseudocode

count = 0
for each cell (r, c):
    if grid[r][c] == '1':
        count++
        dfs(r, c)         // sink the whole island
return count

dfs(r, c):
    if out of bounds OR grid[r][c] != '1': return
    grid[r][c] = '0'       // mark visited in place
    dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

2. Step-by-Step Analysis

Why DFS / BFS works An island is a connected component in the implicit graph (cells = nodes, 4-neighbor adjacency = edges). Counting components = a classic CC algorithm.

Why mutate the grid in place Saves O(m·n) space versus a boolean[][] visited. Acceptable on LeetCode unless you must preserve input.

Why iterate every cell anyway Otherwise we’d miss disconnected islands. The DFS only sinks one island; the outer loop catches the rest.

Counting We increment count once per outer-loop hit on an unsunken '1'. After DFS sinks the island, the inner cells are skipped on later iterations.

ASCII Trace (small grid)

grid:
1 1 0
0 1 0
1 0 1

Outer (0,0)='1' count=1 → DFS sinks (0,0),(0,1),(1,1)
After DFS:
0 0 0
0 0 0
1 0 1

Outer (2,0)='1' count=2 → DFS sinks (2,0)
Outer (2,2)='1' count=3 → DFS sinks (2,2)
return 3

3. Java Solution

DFS

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length, count = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c, m, n);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] g, int r, int c, int m, int n) {
        if (r < 0 || c < 0 || r >= m || c >= n || g[r][c] != '1') return;
        g[r][c] = '0';
        dfs(g, r + 1, c, m, n); dfs(g, r - 1, c, m, n);
        dfs(g, r, c + 1, m, n); dfs(g, r, c - 1, m, n);
    }
}

BFS (Safer for deep stack)

class Solution {
    private static final int[][] DIRS = {{0,1},{1,0},{0,-1},{-1,0}};
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length, count = 0;
        Queue<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    grid[r][c] = '0';
                    q.offer(new int[]{r, c});
                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        for (int[] d : DIRS) {
                            int nr = cur[0] + d[0], nc = cur[1] + d[1];
                            if (nr >= 0 && nc >= 0 && nr < m && nc < n && grid[nr][nc] == '1') {
                                grid[nr][nc] = '0';
                                q.offer(new int[]{nr, nc});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
}

Time: (O(m \cdot n)) Space: (O(m \cdot n)) recursion / queue worst case

4. The “Java vs. Others” Edge

Mutating the grid avoids a boolean[][] visited (saves O(m·n) memory).
ArrayDeque for the BFS queue — faster than LinkedList.
Java has a recursion-depth limit (~10^4); for a grid filled with '1' and m*n very large, prefer BFS.

5. Complexity Summary

Approach	Time	Space	Notes
DFS	O(m·n)	O(m·n) stack	Worst case: filled grid
BFS	O(m·n)	O(min(m,n))	Queue width bounded by perimeter