Number of Islands
Walkthrough video coming soon
The full explanation is written out below — the problem, the intuition, the approach, and the solution code.
The problem
Given an m × n grid of '1' (land) and '0' (water), return the number of islands. An island is land connected 4-directionally (up, down, left, right) and surrounded by water.
Constraints & assumptions
- m == grid.length, n == grid[i].length
- 1 ≤ m, n ≤ 300
- grid[i][j] is '0' or '1'
In plain English
Picture an aerial photo of the sea dotted with land. You want to count separate islands. You scan the photo row by row, and the moment your eye lands on a piece of land you've never visited, you've discovered a new island — so you tick your counter up by one.
Then you pour imaginary paint on it: the paint spreads to every connected land cell and floods the whole island, marking it as visited. Because the entire landmass is now painted over, your scan will never mistakenly count it a second time. Every fresh, unpainted patch of land is exactly one new island.
What you need to know
The programming concepts this problem is built on:
How to approach it
- 1Scan every cell in the grid.
- 2When you hit an unvisited land cell ('1'), increase the island count.
- 3Flood that whole island — visit every connected land cell and mark it as water ('0').
- 4Because the island is now erased, the scan continues and only new islands trigger the counter.
The solutions
2 waysThis one can be solved more than one way. Switch between the methods to compare — each summary explains how it differs.
Recursively sink the island from the cell you found.
From each new land cell we recurse into its four neighbours, flipping land to water as we go. The call stack does the bookkeeping. Compact and elegant, but very large grids could, in theory, recurse deeply.
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[][] 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';
sink(grid, r + 1, c);
sink(grid, r - 1, c);
sink(grid, r, c + 1);
sink(grid, r, c - 1);
}
}