#200
Number of Islands
Medium Connected components on a grid
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a grid of '1' (land) and '0' (water), count islands — groups of land connected up/down/left/right.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many separate groups of land?
Why this works: each time you find new land, count one island and sink the whole island with DFS so it isn't counted again.
Example: 1 1 0 / 0 1 0 / 0 0 1
first island: top-left 3 cellssecond island: bottom-right cell → 2
✦Hints open one at a time
Each time you find unvisited land, that's a new island.
Sink the whole island with DFS/BFS so you don't count it again.
↗Approach
Scan cells. On a '1', increment the count and DFS to set every connected '1' to '0'.
</>Solution (Java)
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1') {
count++;
sink(grid, r, c);
}
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'; // visited
sink(g, r + 1, c);
sink(g, r - 1, c);
sink(g, r, c + 1);
sink(g, r, c - 1);
}
}!Common mistake
Counting diagonal neighbours as connected.
Complexity
- Time: O(m·n).
- Space: O(m·n) worst-case recursion.
Topic: Graphs
🎬 Episodes 74–85: video coming soon