Number of Islands
Number of Islands is a medium graphs problem solved with the connected components pattern.
The best approach, dfs sinking, runs in O(m · n) time and O(m · n) space.
Below are 2 approaches in Java, from bfs per island up.
Problem
Given a grid of '1' (land) and '0' (water), count the islands: groups of land cells connected horizontally or vertically.
Examples
Example 1
- Input
grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]- Output
2
Example 2
- Input
grid = [[0,0],[0,0]]- Output
0
Constraints
1 <= m, n <= 300; cells are '1' (land) or '0' (water).- 4-directional connectivity.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| BFS per island | O(m · n) | O(min(m, n)) |
| DFS sinking | O(m · n) | O(m · n) |
1BFS per island
O(m · n)O(min(m, n))The BFS frontier on a grid is bounded by its smaller side.Scan the grid. On unvisited land, count an island and BFS to mark all its land.
- For each '1': count++, set it to '0', BFS setting neighbours to '0' when enqueued.
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length, count = 0;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != '1') continue;
count++;
grid[i][j] = '0';
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] { i, j });
while (!q.isEmpty()) {
int[] c = q.poll();
for (int[] d : dirs) {
int r = c[0] + d[0], k = c[1] + d[1];
if (r >= 0 && k >= 0 && r < m && k < n && grid[r][k] == '1') {
grid[r][k] = '0';
q.add(new int[] { r, k });
}
}
}
}
return count;
}
}2DFS sinking
O(m · n)O(m · n)Worst-case recursion depth when the grid is all land.Same scan, but sink each island with a recursive DFS that turns its land into water.
- For each '1': count++, sink(i, j).
- sink: bounds and land check; set '0'; recurse 4 ways.
class Solution {
public 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++; sink(grid, i, j); }
return count;
}
private void sink(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';
sink(g, r + 1, c);
sink(g, r - 1, c);
sink(g, r, c + 1);
sink(g, r, c - 1);
}
}Edge cases to test
- All water or all land
- Islands touching only diagonally (separate)
Hints
Hint 1
Every time you find unvisited land, you have found a new island. Sink the whole island so you never count it again.
FAQ
What is the best time complexity for Number of Islands?
DFS sinking runs in O(m · n) time and O(m · n) extra space.
Which pattern does Number of Islands use?
It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces.
Is there a brute force solution for Number of Islands?
Yes. BFS per island takes O(m · n) time and O(min(m, n)) space. Scan the grid.
Which edge cases should I test for Number of Islands?
All water or all land; Islands touching only diagonally (separate).