Graphs · LC #200
Number of Islands
Count connected land regions in a 2-D char grid using DFS flood-fill that marks visited cells, avoiding double-counting.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an `m x n` 2D binary grid of `'1'` (land) and `'0'` (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Sample I/O
Input: [["1","1","0","0"],
["1","1","0","0"],
["0","0","1","0"],
["0","0","0","1"]]
Output: 3Intuition
How to Think About It
Intuition
Each unvisited land cell is the seed of a new island. DFS/BFS from that cell marks all reachable connected land as visited ('0'). Because marking is in-place, subsequent iterations skip already-processed cells - each cell is visited at most once.
Core Concept
Flood-fill DFS. Iterate every cell. On finding '1': increment count, launch DFS that recursively marks all 4-directional '1' neighbors as '0'. After DFS, the entire island is consumed. Continue scanning - remaining '1' cells start new islands.
When to use
Counting or labeling connected components in a 2-D grid; any problem requiring visiting all cells in a region; flood-fill painting; BFS variant for shortest path within a region.
When NOT to use
When the grid is too large for stack-based DFS (deep recursion → stack overflow) - use iterative BFS or Union-Find instead. When the grid must not be mutated - use a separate visited boolean array.
Key Insights
What to Know Cold
- Marking cells as '0' (or using a visited set) is mandatory - without it, infinite recursion or double-counting occurs.
- BFS and DFS produce the same count; BFS avoids stack overflow on large grids.
- Union-Find is the third approach: union adjacent land cells, count distinct components at the end.
- The 4-directional constraint (not 8) means diagonal land cells are NOT connected.
- The same pattern applies to any grid-connectivity problem: Max Area of Island, Pacific Atlantic, surrounded regions.
1 example
Worked Examples
DFS flood-fill
4×4 grid with 3 disjoint land clusters.
Scan cell-by-cell; DFS from each unvisited '1'; mark as '0'; count++.
function numIslands(grid: string[][]): number {
function dfs(i: number, j: number) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] !== '1') return;
grid[i][j] = '0';
dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1);
}
let count = 0;
for (let i = 0; i < grid.length; i++)
for (let j = 0; j < grid[0].length; j++)
if (grid[i][j] === '1') { dfs(i, j); count++; }
return count;
}Output: 3
One of the most frequently asked medium graph problems across all Mag7 companies. Interviewers test DFS mechanics, boundary checks, and whether you explain the visited-marking invariant.