Number of Islands
Count how many connected land components appear in a binary grid.
Problem Summary
Original task summary for this archive page. The official LeetCode prompt is linked in the header instead of being mirrored here.
You are given a binary grid where land cells form islands through four-directional adjacency. Count how many separate islands exist.
The hard part is not detecting land. It is making sure an entire connected component is counted exactly once.
Recognition Pattern
How to notice the underlying interview pattern before writing code.
This is a DFS/BFS + visited problem on a grid.
In interviews, recognize it when:
the input is a 2D grid
cells connect through fixed directions such as up, down, left, and right
the question asks for connected components, reachability, or flood fill
Key Idea
The main invariant or observation that makes the clean solution work.
Scan the grid cell by cell. Whenever you find unvisited land, that land must belong to a new island, so increment the answer and flood-fill the entire component.
The flood fill marks every cell in that island as visited. After that, the outer scan can safely ignore those cells, so each island contributes exactly one count.
For this problem, mutating the grid from `'1'` to `'0'` is the simplest visited-marking strategy.
Step-by-step Reasoning
How to move from the obvious brute-force idea to the interview-ready solution.
The naive mistake is to count every land cell, but that clearly overcounts multi-cell islands.
The next observation is structural: two land cells belong to the same island precisely when they are in the same connected component under four-directional movement.
That reframes the task as a standard graph problem. The grid is just an implicit graph where each land cell has up to four neighbors. Once you see that, DFS or BFS is the natural tool: start at one land cell, visit everything reachable from it, and treat that whole region as one island.
Complexity
Time and memory costs for the implementation shown below.
Time: \(O(mn)\)
Space: \(O(mn)\) in the worst case due to the recursion stack
C++ Solution
The exact repository source used for this LeetCode solution page.
#include <vector>
class Solution {
public:
int numIslands(std::vector<std::vector<char>>& grid) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
int islandCount = 0;
for (int row = 0; row < rows; ++row) {
for (int column = 0; column < columns; ++column) {
if (grid[row][column] != '1') {
continue;
}
++islandCount;
eraseIsland(grid, row, column);
}
}
return islandCount;
}
private:
void eraseIsland(std::vector<std::vector<char>>& grid, int row, int column) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
if (row < 0 || row >= rows || column < 0 || column >= columns || grid[row][column] != '1') {
return;
}
grid[row][column] = '0';
eraseIsland(grid, row + 1, column);
eraseIsland(grid, row - 1, column);
eraseIsland(grid, row, column + 1);
eraseIsland(grid, row, column - 1);
}
};
Common Pitfalls
Real implementation mistakes that show up often in interviews and submissions.
Only four-directional neighbors count. Diagonals do not connect islands here.
Mark a cell as visited before exploring neighbors, otherwise cycles cause repeated work.
Mutating the grid is clean here, but in other interview settings you may need a separate `visited` matrix if the input must stay unchanged.
Variants / Follow-ups
Nearby problems and the next generalization to learn once this pattern is stable.
This pattern leads directly to Max Area of Island, Surrounded Regions, Flood Fill, and Number of Provinces.
The reusable idea is to translate a grid into component traversal instead of treating each cell as an isolated local decision.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.