Number of Islands
Count connected components of '1's in a grid. BFS/DFS or Union-Find — both O(m·n).
graphbfsdfsunion-find
Intro
Given a grid of '1' (land) and '0' (water), count the number of islands. Each cell is connected to its 4-directional neighbours.
Key insight
Each unvisited '1' starts a new island; a flood-fill marks the whole component as visited.
Approach
- 1Iterate every cell.
- 2On an unvisited '1', increment island count and BFS/DFS to mark the whole component.
- 3Mark by writing '0' to the grid (in-place) or using a visited[][] matrix.
Complexity
Time
O(m · n)
Space
O(m · n) worst case stack/queue
Code
Snippetjava
int numIslands(char[][] g) {
int count = 0, m = g.length, n = g[0].length;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (g[i][j] == '1') { count++; dfs(g, i, j); }
return count;
}
void dfs(char[][] g, int r, int c) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
g[r][c] = '0';
dfs(g, r+1, c); dfs(g, r-1, c); dfs(g, r, c+1); dfs(g, r, c-1);
}Pitfalls
- DFS recursion depth on a giant grid can blow the stack — use BFS or iterative DFS for very large m·n.
- Comparing chars to ints (e.g., `g[i][j] == 1` instead of `'1'`).
Variants & follow-ups
- Max Area of Island (LC 695)
- Number of Distinct Islands (LC 694)