Number of Islands Problem: How Would You Solve It?
Learn how to solve the number of islands problem with DFS/BFS flood-fill, complexity analysis, and the union-find alternative.
Expected Interview Answer
Number of islands is solved by scanning the grid and, each time an unvisited land cell is found, running a flood-fill (DFS or BFS) that marks every orthogonally connected land cell as visited, then incrementing an island counter once per flood-fill launch, because each launch corresponds to discovering exactly one previously unseen connected component.
The grid is treated as an implicit graph where land cells are nodes and orthogonal adjacency between two land cells is an edge; islands are exactly the connected components of this graph. Iterating over every cell and skipping ones already visited or that are water guarantees each connected component is only counted once, since the flood-fill triggered on first contact consumes the entire component before the outer scan continues. Using DFS with recursion or an explicit stack, or BFS with a queue, both work correctly and run in O(rows * cols) time since every cell is visited a constant number of times; the choice mostly affects call-stack depth versus queue memory. Marking cells visited in place, for example by flipping land to a sentinel value, avoids needing a separate visited matrix and keeps space overhead to the recursion or queue itself.
- O(rows * cols) time, each cell visited a constant number of times
- Directly models islands as connected components of an implicit graph
- Works identically with DFS or BFS flood-fill
- In-place marking avoids extra visited-matrix memory
AI Mentor Explanation
Picture a stadium seating chart where blocks of seats sold to the same fan club form a cluster, and adjacent sold seats belong to the same cluster while empty seats separate clusters. A steward scans the chart row by row, and the moment an unmarked sold seat is found, floods outward marking every orthogonally connected sold seat as belonging to that one cluster before moving on. Each flood corresponds to exactly one distinct fan-club cluster, so the steward increments the cluster count once per flood launch, never for individual seats within it. Skipping seats already marked or empty is what guarantees each cluster of connected sold seats is counted exactly once.
Step-by-Step Explanation
Step 1
Scan the grid cell by cell
Iterate every row and column; skip cells that are water or already visited.
Step 2
Launch flood-fill on new land
When an unvisited land cell is found, start a DFS or BFS from it.
Step 3
Mark the entire connected component
The flood-fill visits every orthogonally connected land cell and marks each one visited before returning.
Step 4
Increment the counter once per flood
Each flood-fill launch corresponds to exactly one island; increment the counter once, not per cell.
What Interviewer Expects
- Frame islands as connected components of an implicit graph
- State the O(rows * cols) time complexity clearly
- Explain why the counter increments once per flood-fill, not per cell
- Mention either DFS or BFS works, and discuss recursion depth risk for very large grids
Common Mistakes
- Incrementing the counter for every land cell instead of once per connected component
- Forgetting to mark cells visited, causing infinite recursion or double counting
- Allowing diagonal connections when the problem specifies orthogonal adjacency only
- Using a separate visited matrix when in-place marking would save space
Best Answer (HR Friendly)
“I scan the grid, and whenever I hit a land cell I have not seen yet, I flood outward and mark every connected land cell as visited, which is one island. I count once per flood-fill, not once per cell, and since every cell is only visited a constant number of times, the whole scan runs in linear time relative to the grid size.”
Code Example
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
count = 0
def flood(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != "1":
return
grid[r][c] = "0"
flood(r + 1, c)
flood(r - 1, c)
flood(r, c + 1)
flood(r, c - 1)
for row in range(rows):
for col in range(cols):
if grid[row][col] == "1":
count += 1
flood(row, col)
return countFollow-up Questions
- How would you solve this with union-find instead of DFS/BFS?
- How would you count the number of distinct island shapes rather than just islands?
- How would you handle a grid too large to fit in memory, streamed row by row?
- How does allowing diagonal adjacency change the algorithm and the result?
MCQ Practice
1. How is an island counted using flood-fill DFS?
Each flood-fill launch corresponds to exactly one connected component (island), so the counter increments once per launch.
2. What is the time complexity of the number of islands algorithm?
Every cell is visited a constant number of times across the scan and flood-fills, giving O(rows * cols) time.
3. What alternative to DFS/BFS can also solve number of islands?
Union-Find can union adjacent land cells and count the number of resulting disjoint sets as the island count.
Flash Cards
What structure does the number of islands problem model? — Connected components of an implicit graph where land cells are nodes and adjacency is an edge.
When does the island counter increment? — Once per flood-fill launch, since each launch consumes exactly one connected component.
What is the time complexity? — O(rows * cols), since every cell is processed a constant number of times.
Name an alternative algorithm to DFS/BFS flood-fill. — Union-Find (Disjoint Set Union), unioning adjacent land cells and counting resulting sets.