Number of Islands
The Prompt
Given an `m x n` 2D binary grid `grid` which represents a map of `1`s (land) and `0`s (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Understanding the Problem
Read the grid as a graph: every '1' cell is a node, and horizontally or vertically adjacent '1's are connected. An island is then exactly a connected component of land cells, and the answer is the number of components.
The counting scheme: scan the grid cell by cell. Each time you hit an unvisited '1', you have discovered a brand-new island — increment the count, then flood-fill (DFS or BFS) from that cell to mark every land cell it connects to, so the rest of the scan never counts this island again.
The Interview Flow
Interviewer
Given a 2D grid of 1s and 0s, how would you count the number of islands?
Candidate
I can treat the grid as a graph where each '1' is a node. I need to find the number of connected components of these '1' nodes.
Interviewer
How would you find the connected components?
Candidate
I would iterate through every cell of the grid. If I find a cell containing a '1', it means I've found a piece of an island. I'll increment my island count. Then, I need to find all the other connected '1's that belong to this same island and mark them as visited so I don't count them again.
Interviewer
How do you find and mark all parts of that island?
Candidate
I can use a graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS). Starting from the initial '1' I found, I'll explore all its adjacent (horizontally and vertically) land cells. A simple way to mark them is to change their value from '1' to something else, like '0' or '#'. This "sinks" the island, ensuring I don't recount it.
Interviewer
So the overall algorithm would be?
Candidate
Iterate through the grid. If `grid[i][j]` is '1', increment count, and then start a DFS or BFS from `(i, j)` to visit and sink all parts of that island. Then continue the iteration until I've checked every cell.
Interviewer
That's a perfect strategy. Please implement it using DFS.
Why does flood-filling on first contact count each island exactly once?
The invariant: at any point in the scan, the count equals the number of distinct components touched so far, and every cell of a touched component is marked visited. When the scan hits an unmarked '1', it must belong to a never-seen component — so incrementing is correct — and the flood fill restores the invariant by marking the whole component before the scan resumes.
Every cell is scanned once and flood-filled at most once, 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 (a grid that is all land).
DFS-based Grid Traversal
- Initialize `islandCount` to 0.
- Iterate through each cell `(r, c)` of the grid.
- If `grid[r][c]` is '1':
- Increment `islandCount` by 1.
- Call a helper function, `dfs(grid, r, c)`, to find and "sink" all parts of this island.
- **DFS Helper Function `dfs(grid, r, c)`:**
- Check for boundary conditions: if `r` or `c` is out of bounds, or if `grid[r][c]` is '0' (water) or already visited, simply return.
- Mark the current cell as visited by changing its value, e.g., `grid[r][c] = '0'`.
- Recursively call `dfs` for all four adjacent cells: `(r+1, c)`, `(r-1, c)`, `(r, c+1)`, and `(r, c-1)`.
- After iterating through all cells, return `islandCount`.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function numIslands(grid) {
if (!grid || grid.length === 0) {
return 0;
}
let islandCount = 0;
const rows = grid.length;
const cols = grid[0].length;
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
return;
}
grid[r][c] = '0'; // Sink the island
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
islandCount++;
dfs(r, c);
}
}
}
return islandCount;
}Explanation
Grid [[1,1,0],[0,1,0],[0,0,1]] — four land cells forming two islands.
1The grid as a graph: land cells (0,0), (0,1), (1,1) chain together via shared edges, while (2,2) sits alone — its neighbors are all water. The scan starts at (0,0) and finds an unvisited '1'.
2New land found → count = 1, then flood fill: DFS from (0,0) visits (0,1) and (1,1), marking all three. The scan continues past (0,1) and (1,1) without incrementing — they are already claimed.
3The scan reaches (2,2): unvisited land again → count = 2. Its flood fill marks only itself (no land neighbors). The scan finishes with every cell examined once — answer: 2 islands.
Complexity Analysis
TIME
O(m * n)
SPACE
O(m * n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.