Number of Islands
Scan the grid. When you find a '1', that's a new island — run DFS/BFS to mark all connected '1's as visited (sink them to '0'). The number of times you trigger DFS/BFS = number of islands.
How It Works
Treat the grid as an implicit graph: each land cell is a node and horizontally or vertically adjacent land cells are connected. Scan the grid left to right, top to bottom. Every time you encounter an unvisited '1', you have discovered a new island — increment the count, then flood-fill from that cell with DFS or BFS, marking every reachable land cell as visited (commonly by sinking it to '0'). Later scan positions inside the same island are already marked, so they never trigger a second count.
Each cell is visited a constant number of times — once by the scan and at most once by a flood fill — so the total work is O(m*n) time. Space is O(m*n) in the worst case for the recursion stack or BFS queue (one snake-shaped island), and mutating the grid in place avoids a separate visited array.
Step-by-Step Visualization
Code
static int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++)
for (int j = 0; j < grid[0].length; j++)
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
return count;
}
static void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
grid[i][j] = '0';
dfs(grid, i+1, j); dfs(grid, i-1, j);
dfs(grid, i, j+1); dfs(grid, i, j-1);
}Tips & Gotchas
Practice Problems
- 1Number of Islands
- 2Max Area of Island
- 3Surrounded Regions
- 4Number of Closed Islands
About the Matrix DP & BFS Pattern
Many grid problems are graph problems in disguise. Each cell is a node, adjacent cells are edges. Use BFS for shortest paths, DFS for connectivity, or DP for optimal paths.
For traversal: use direction arrays dx=[0,0,1,-1], dy=[1,-1,0,0]. For sorted matrix search, start from top-right corner. For grid DP, fill row by row — current cell depends on top and left.
Common Matrix Interview Problems
- Spiral Matrix
- Rotate Image
- Search a 2D Matrix
- Number of Islands
- Maximal Square
- Set Matrix Zeroes
- Word Search
Frequently Asked Questions
Should I use DFS, BFS, or Union-Find for island counting?
All three are O(m*n) and any is acceptable for a static grid; recursive DFS is the shortest to write but can overflow the stack on huge grids, where BFS or iterative DFS is safer. Union-Find shines in the dynamic variant (Number of Islands II) where land is added over time and recomputing from scratch would be too slow.
What if I am not allowed to modify the input grid?
Keep a separate boolean visited matrix of the same dimensions and mark cells there instead of sinking them. The complexity is unchanged; you simply pay O(m*n) extra space explicitly rather than reusing the grid as your marker.
Do diagonal neighbors count as connected?
In the standard problem, no — connectivity is 4-directional. Some variants use 8-directional adjacency, so always confirm before coding; the only change is the set of neighbor offsets you iterate.