Number of Islands: The Grid DFS Flood-Fill Pattern
Count islands in a binary grid with recursive DFS flood fill — intuition, JavaScript code, a worked walkthrough, complexity analysis, and the mistakes to avoid.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Number of Islands is where most people first realize a 2D grid is a graph. Every '1' is a node, every side-by-side pair of land cells is an edge, and an "island" is just a connected component. Once you see that, the problem stops being a puzzle about maps and becomes a template you'll reuse for maze solving, region coloring, and dozens of matrix-traversal questions.
The trick that makes it clean isn't the traversal itself — it's what you do after you visit a cell. Instead of tracking visited cells in a separate structure, you sink each piece of land as you touch it, turning '1' into '0'. The grid becomes its own visited-set.
The problem
You're given an m x n binary grid where '1' is land and '0' is water. An island is a group of land cells connected horizontally or vertically (never diagonally), surrounded by water or the grid edge. Count how many distinct islands exist.
Input:
1 1 0
1 0 0
0 0 1
Output: 2The top-left L-shaped blob — cells (0,0), (0,1), (1,0) — is one island because those three cells touch edge-to-edge. The lone '1' at (2,2) is a second island. Diagonal contact doesn't count, so it stays separate.
Two constraints shape the whole solution:
- Only 4-directional adjacency counts — up, down, left, right. Not diagonals.
- Each land cell belongs to exactly one island — so once you've assigned a cell to an island, you must never count it again.
The brute force baseline
The instinct most people reach for is a separate visited matrix. Walk every cell; when you hit unvisited land, run a traversal that marks every connected cell as visited in that side structure.
function numIslands(grid) {
const rows = grid.length, cols = grid[0].length;
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
if (grid[r][c] === '0' || visited[r][c]) return;
visited[r][c] = true;
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' && !visited[r][c]) { count++; dfs(r, c); }
}
}
return count;
}This is correct and already runs in O(m·n) time — the traversal isn't the problem. The waste is the extra visited grid: a full second m x n array of booleans just to remember where you've been. When the input grid is already sitting in memory and mutable, that second structure is redundant.
The key insight: the grid is its own visited-set
You don't need a parallel visited array — you need a way to mark a land cell as "already counted" so the scan never revisits it. The grid already gives you a spare symbol for that: '0'.
So when DFS reaches a land cell, sink it — overwrite grid[r][c] with '0'. Now the boundary check that stops you at water does double duty: it also stops you at any land you've already flooded. This is the flood-fill pattern, the same idea behind a paint-bucket tool: pick a seed, then recursively spill into every connected cell of the same type, converting as you go.
The outer scan then reads like a definition: every time you find a '1' that hasn't been sunk yet, it must be the first cell of a brand-new island, so bump the count and flood the rest of it away.
The optimal solution
function numIslands(grid) {
if (!grid || grid.length === 0) return 0;
let count = 0;
const rows = grid.length;
const cols = grid[0].length;
function dfs(r, c) {
// Boundary and water check
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
return;
}
// Mark as visited (sink the island part)
grid[r][c] = '0';
// Recursive flood fill in 4 directions
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') {
count++;
dfs(r, c);
}
}
}
return count;
}Everything hinges on the single dfs guard. One combined condition handles all four ways a call can be invalid: off the top or bottom (r < 0 || r >= rows), off the left or right (c < 0 || c >= cols), or landing on water/already-sunk land (grid[r][c] === '0'). If any is true, the call returns immediately. Otherwise it sinks the cell and recurses into all four neighbors. There's no separate visited array — sinking to '0' is the visited mark.
Walkthrough
Tracing the grid from above. The outer loop scans cells left-to-right, top-to-bottom. Only the state that changes is shown.
| Scan cell | grid value there | Action | Islands |
|---|---|---|---|
| (0,0) | '1' | New island → count = 1, run DFS from (0,0) | 1 |
| (0,1) | '0' | Already sunk by the DFS below — skip | 1 |
| (0,2) | '0' | Water — skip | 1 |
| (1,0) | '0' | Already sunk — skip | 1 |
| (1,1) | '0' | Water — skip | 1 |
| (1,2) | '0' | Water — skip | 1 |
| (2,0) | '0' | Water — skip | 1 |
| (2,1) | '0' | Water — skip | 1 |
| (2,2) | '1' | New island → count = 2, run DFS from (2,2) | 2 |
The DFS launched at (0,0) is what makes every cell after it read as '0'. It sinks (0,0), then spills down to (1,0) and right to (0,1), sinking both; each of their neighbors is water, an edge, or already '0', so the recursion unwinds. After that one DFS the grid looks like:
0 0 0
0 0 0
0 0 1The scan continues over nothing but zeros until it reaches (2,2), the second seed. Its DFS sinks that single cell, and the loop ends with count = 2. Every land cell was touched exactly once — either as a scan-loop seed or inside a DFS.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
Separate visited matrix | O(m·n) | O(m·n) | visits each cell once, but stores a second full grid |
| In-place flood fill | O(m·n) | O(m·n) worst case | each cell visited once; space is the recursion stack, not a side array |
| BFS flood fill (queue) | O(m·n) | O(min(m,n)) | queue holds at most a frontier, not a full DFS chain |
Every cell is examined a constant number of times — once by the outer scan and up to four times as a neighbor — so time is O(m·n). The in-place version's space is the DFS recursion depth, which in the worst case (one giant snake-shaped island filling the grid) can reach O(m·n) call frames. If deep recursion is a concern, the BFS variant caps auxiliary space at O(min(m, n)).
Common mistakes
- Checking bounds after indexing. If you read
grid[r][c]before verifyingrandcare in range, an out-of-bounds recursive call throws or readsundefined. The single guard checks bounds first, then the cell value — order matters. - Adding diagonals. Recursing into
(r+1, c+1)and friends merges diagonally-touching cells into one island. The problem defines connectivity as 4-directional only; eight directions is a different problem. - Forgetting to sink the cell. Skip the
grid[r][c] = '0'line and the DFS revisits the same cells forever — infinite recursion and a stack overflow. The sink is the base case that terminates the flood. - Restoring the grid mid-count. Some people sink a cell, recurse, then set it back to
'1'(backtracking style). That's for path-counting problems; here it lets the outer scan re-seed the same island and inflate the count. - Assuming a rectangular non-empty grid. Guard the empty case (
grid.length === 0) before readinggrid[0].length, or an empty input crashes.
Where this pattern shows up next
Grid-as-graph DFS and connected-component counting generalize straight into the rest of the graph track:
- Shortest Path in Binary Matrix — the same grid-as-graph model, but BFS for shortest distance instead of DFS for counting.
- Redundant Connection — connected components again, solved with Union-Find, the other standard tool for "which things are joined?".
- Course Schedule II — DFS on an explicit graph, this time to produce a topological order.
- Network Delay Time — weighted-graph traversal, where plain DFS gives way to Dijkstra.
You can also step through Number of Islands interactively to watch the scan find each seed and the flood fill sink a whole island at a time.
FAQ
Why does sinking cells to '0' work instead of a visited array?
Because the only reason to track visited cells is to avoid counting the same island twice, and overwriting land with '0' accomplishes exactly that. The DFS boundary check already stops at '0', so a sunk cell is automatically treated as off-limits on any later visit. It saves an entire m x n boolean array — the trade-off is that you mutate the input grid, which is fine when the caller doesn't need it afterward.
What is the time and space complexity of Number of Islands?
Time is O(m·n) because every cell in the grid is processed a constant number of times — once by the outer scan and at most four times as a DFS neighbor. Space for the recursive DFS version is O(m·n) in the worst case, driven by recursion depth when a single island snakes through the whole grid. A BFS variant with an explicit queue lowers auxiliary space to O(min(m, n)).
Can I solve Number of Islands with BFS instead of DFS?
Yes. Replace the recursive flood fill with a queue: push the seed cell, then repeatedly pop a cell, sink it, and enqueue its four in-bounds land neighbors. BFS produces the same island count and avoids deep recursion, so it's the safer choice on very large grids where a DFS call stack could overflow. The outer scan and the sink-to-'0' trick stay identical.
Why don't diagonally adjacent land cells form one island?
The problem defines an island as land connected horizontally or vertically only. That's why the DFS recurses into exactly four neighbors — up, down, left, right — and never the four diagonals. Two '1's touching only at a corner have no edge between them in this graph model, so they're counted as separate islands. Adding diagonal recursion would solve a different, looser connectivity problem.
Does the algorithm modify the input grid?
Yes, the in-place version overwrites every land cell it counts with '0', so the grid is all water by the time the function returns. If you must preserve the original input, either clone the grid first, use a separate visited matrix instead of sinking, or restore each cell after the full count (not during the DFS, which would corrupt the count). For interview purposes, mutating in place is standard and usually expected.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.