Number of Islands — DFS Flood Fill
Treat the grid as a graph; whenever you encounter land, run DFS/BFS to sink the entire island and increment the count.
Problem Statement
Count the number of connected groups of 1s in a grid using four-directional adjacency.
Why This Problem Matters
- Canonical flood fill problem for practicing graph traversal.
- Builds intuition for island/region counting variations.
- Demonstrates the utility of marking visited nodes to avoid rework.
Thought Process
Scan every cell
When a land cell is found, increment islands and start a traversal to mark the whole island.
Mutate grid or track visited
To avoid revisiting nodes, either change 1s to 0s in place or use a visited boolean grid.
Use DFS/BFS interchangeably
Either recursion or a queue works; choose based on stack depth comfort.
Step-by-Step Reasoning
- Initialise count = 0.
- For each cell, if it is land, increment count and call dfs to sink it.
- DFS explores four neighbors, stopping when out of bounds or hitting water.
- Continue scanning grid until completion.
Dry Run
Grid with three separated land masses
DFS invoked three times, resulting count 3.
All water grid
Count remains zero; DFS never called.
Complexity Analysis
Time
O(m·n)
Space
O(m·n)
Why
Each cell visited at most once; recursion depth equals largest island size.
Annotated Solution
public class NumberOfIslands {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int numIslands(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int r = 0; r < rows; r += 1) {
for (int c = 0; c < cols; c += 1) {
if (grid[r][c] == '1') {
count += 1;
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] != '1') {
return;
}
grid[r][c] = '0';
for (int[] dir : DIRS) {
dfs(grid, r + dir[0], c + dir[1]);
}
}
}Mutating the grid in-place keeps memory usage low and guarantees each cell is processed once.
Common Pitfalls
- Forgetting to mark visited cells causes exponential loops.
- Not handling recursion limits; consider iterative BFS for very large grids.
- Diagonal adjacency is not allowed; emphasise Manhattan neighbors only.
Follow-Up Questions
- How would you count island perimeters or sizes?
- Can you solve the same problem using union-find?