Number of Islands: A Step-by-Step Interview Walkthrough
- 3 days ago
- 14 min read
Number of Islands is a common interview problem because it tests a specific cognitive move: can you recognize that a problem presented in one form is actually a different problem in disguise? The 2D grid framing is intuitive — humans naturally think of grids as visual things — but the underlying problem is counting connected components in a graph. Candidates who treat the grid as just a grid often write convoluted code with manual neighbor tracking, custom adjacency rules, and ad-hoc visited-set logic. Candidates who recognize "this is a graph traversal" immediately reach for DFS or BFS and finish in fifteen lines. The signal here is whether you can map between representations — see past the surface presentation to the underlying structure.
Connected-components computation underpins image segmentation in computer vision (identifying distinct objects in a labeled image), flood-fill tools in image editors, region detection in geographic information systems, cluster identification in social networks, and connected-region analysis in materials science and medical imaging. The same grid-to-graph reframing that solves Number of Islands also solves many real-world problems where the data happens to be 2D but the question is fundamentally about connectivity.
Problem Statement
Given a 2D grid of characters '1' (land) and '0' (water), return the number of islands.
An island is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
Example:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1Returns 3.
1. Clarify Requirements Before Jumping Into Code
Let's start by restating the problem in our own words and ask the kinds of questions that would change our approach.
Input: a 2D grid of characters where '1' is land and '0' is water.
Output: an integer — the count of distinct islands.
Details to clarify:
Does diagonal adjacency count? No — only horizontal and vertical (4-directional). This is critical; the algorithm changes if diagonals matter.
Are we allowed to modify the input grid? Usually yes — and saying so up front simplifies the implementation considerably. Worth asking explicitly.
Can the grid be empty? Yes — return 0.
Can rows have different lengths? Generally no, but worth confirming for production code.
Are '1' and '0' characters or integers? Characters (single quotes in the problem), which matters for comparisons in code.
The thing to flag is the 4-directional adjacency rule. It's the constraint that defines what counts as "the same island," and it's also the constraint that maps cleanly onto a graph: each land cell has up to four neighbors (up, down, left, right), and those edges are what we'll traverse.
2. Identify the Category of the Question
A few signals jump out:
We're counting connected groups of cells.
Cells are connected via a simple adjacency rule.
The exact shape or size of each group doesn't matter — only how many distinct groups exist.
That combination — counting groups, adjacency-based connectivity, indifference to internal structure — is the fingerprint of a connected-components problem. In graph terms: build a graph where each land cell is a node and each adjacency pair is an edge, then count how many connected components contain land. The "grid" presentation is just a convenient way of describing the graph implicitly — we never have to build the graph explicitly because the adjacency rule lets us derive neighbors on the fly.
Same family as Surrounded Regions, Max Area of Island, Pacific Atlantic Water Flow, and Word Search. Once you internalize "grids are often graphs," a whole class of problems collapses into a uniform technique.
3. Brute Force Solution
Let's start with the most direct approach. We'll scan every cell, and for each land cell we find, we run a search outward to mark every reachable land cell as part of this island, increment the count, and move on.
The "search outward" part can be naive — for every land cell, look at its four neighbors, add them to a list to process, look at their neighbors, and so on. This is essentially what BFS or DFS does, but we'd be running it from scratch each time.
The bigger question for the brute force is: how do we avoid counting the same island twice? If we naively scan cells and start a search at every land cell we encounter, we'd start a new "search" for every cell in a 100-cell island, and we'd count that island 100 times.
The fix is to track visited cells. Once we've explored a cell as part of some island, we mark it so future scans skip it. That marking can live in a separate boolean matrix, or — if we're allowed to modify the input — we can overwrite visited land cells with '0' directly. The second approach saves memory and is often cleaner to write.
The brute force teaches us two things worth keeping: (1) the algorithm is fundamentally "scan, search, mark visited," and (2) the marking has to happen during each search, not after, or we'll over-count when the outer scan revisits cells we've already explored.
4. Brainstorm More Solutions
Step 1: Reframe the grid as a graph
Let's think about what the problem is actually asking. We need to count "islands," where an island is a group of land cells connected through horizontal and vertical adjacency. The word "connected" is doing real work here — it implies a relationship between cells, not just a property of individual cells. Counting islands means counting these groups of related things, not just counting cells. So at minimum, we need a way to talk about which cells are related to which, and we need a way to count distinct groups.
That's exactly what graphs are for. A graph is just "a set of things plus a set of connections between them," and a connected component is "the maximal group of things reachable from each other through those connections." Once we phrase the problem in those terms — things, connections, groups — the match is exact: cells are the things, the 4-directional adjacency rule defines the connections, and each island is a connected component. We're not forcing a graph view onto the problem; we're recognizing that "islands" was already the informal name for connected components all along.
So let's formalize our understanding of the graph in this problem. Every land cell is a node. Two land cells are connected by an edge if they're adjacent horizontally or vertically. An island is exactly a connected component of this graph — a maximal set of land cells reachable from each other through adjacency. The question "how many islands are there?" is literally "how many connected components does this graph have?"
We don't need to build the graph as an explicit adjacency list. The grid is the adjacency information — given a cell at (r, c), its neighbors are at (r±1, c) and (r, c±1), provided those positions are inside the grid bounds. We compute neighbors on the fly.
This reframing is the entire conceptual leap. Once we see the grid as a graph, we know the algorithm: standard connected-components counting via DFS or BFS.
Step 2: The algorithm
Here's the standard algorithm for counting connected components:
Iterate over every cell in the grid.
When we find an unvisited land cell:
Increment the island counter.
Run a search (DFS or BFS) that visits every land cell reachable from this one, marking each as visited.
Return the counter.
The inner search "consumes" an entire island in one go, marking every cell so the outer scan won't trigger another search on those cells later. The outer scan is what counts distinct islands; the inner search is what prevents double-counting.
In code shape:
count = 0
for each cell (r, c) in grid:
if grid[r][c] == '1':
count++
floodFill(r, c)
return count
floodFill(r, c):
if (r, c) is out of bounds: return
if grid[r][c] != '1': return # water or already visited
grid[r][c] = '0' # mark visited by sinking
floodFill(r - 1, c)
floodFill(r + 1, c)
floodFill(r, c - 1)
floodFill(r, c + 1)Step 3: Why marking has to come before the recursive calls
There's a subtle correctness detail worth pausing on: we set grid[r][c] = '0' before recursing into the four neighbors. Why does the order matter?
Imagine we recursed first and marked afterward. The first call recurses into the right neighbor, which is also land. That right neighbor recurses into its left neighbor — which is the original cell, still marked '1'. Now we'd recurse back into the original cell, recurse right again, and bounce between the two cells forever. Infinite loop, stack overflow.
Marking the cell before recursing is what breaks the cycle. By the time the recursive calls run, the cell that triggered them is already '0', so the in-bounds-and-still-land check at the top of each call rejects revisits. This is the same principle as marking nodes "visited" in a standard graph traversal — the marking has to happen at the moment we first see the node, not after we've finished exploring its neighbors.
Step 4: DFS or BFS — does it matter?
Both DFS and BFS solve this problem with the same time and space complexity. The choice is mostly stylistic.
DFS is more concise — four recursive calls in a function — and matches how most candidates instinctively think about flood fill. The downside is that recursion depth equals the longest path through any island, which for a pathological snake-shaped island can equal the total number of land cells. On adversarial grids (say, 1000 × 1000 with a single snake-shaped island), that could blow the call stack.
BFS uses a queue instead of recursion. The queue's maximum size is bounded by the perimeter of the island, which is usually much smaller than the longest path. For most grids, BFS uses less peak memory and avoids stack overflow risk entirely.
Step 5: Walk through the example
Let me trace the algorithm on:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1The outer scan starts at (0, 0):
(0, 0) is '1'. Increment count to 1. Start DFS.
DFS sinks (0, 0), then recurses. The flood reaches (0, 1), (1, 0), (1, 1) — all the cells of the top-left 2×2 block — and marks them all '0'. Returns.
Continue scanning. (0, 1) through (1, 1) are now '0', skipped.
(2, 2) is '1'. Increment count to 2. DFS sinks just that one cell (no land neighbors).
(3, 3) is '1'. Increment count to 3. DFS sinks (3, 3) and (3, 4).
Final count: 3. Matches the expected answer.
Notice how the outer scan only triggered three searches even though it visited many more land cells in total. The marking inside each DFS ensured the outer scan skipped land that had already been claimed by an earlier island. That's the entire mechanism.
Step 6: Complexity
Every cell is visited at most twice: once by the outer scan, and at most once by an inner DFS/BFS call. Total work is O(m × n) where m and n are the grid dimensions.
Space complexity for DFS is O(m × n) in the worst case for the recursion stack — when a single snake-shaped island fills the grid, the recursion depth equals the number of land cells. BFS uses O(min(m, n)) space in the average case (queue size bounded by island perimeter), but can also reach O(m × n) for adversarial inputs.
If we're not allowed to modify the input, we'd need a separate visited matrix, adding O(m × n) space. In-place marking is the cleanest because it reuses the input as the visited tracker.
Potential Follow-up: Union-Find
Suppose you've solved the basic problem and the interviewer follows up: "what if cells could be added or removed dynamically, and you needed to maintain the island count after each change?"
Suddenly our DFS/BFS approach is in trouble. To answer the island count after each change, we'd have to re-scan the entire grid and re-run the whole algorithm from scratch. For k updates on an m × n grid, that's O(k × m × n) work — and the work scales with the whole grid even though each update only affects one cell and its immediate neighbors. We're doing global recomputation in response to local changes. That's the inefficiency the follow-up is asking us to fix.
So the right question is: when a single cell flips from water to land, what information do we actually need? Just two things — which existing islands (if any) it borders, and how to update our count to reflect any merges.
If the new land cell has no land neighbors, it's a new island on its own (count goes up by 1).
If it has neighbors belonging to one existing island, it joins that island (count stays the same).
If it has neighbors belonging to multiple existing islands, those islands now merge into one through this new cell (count goes down by the number of islands merged, minus 1).
That mental model tells us what we need from our data structure: it has to answer "which group is this cell in?" quickly, and it has to support "merge these two groups into one" quickly. We don't need to enumerate the contents of a group or walk through it — we just need group identity and the ability to combine groups.
Once we phrase the requirements that way, Union-Find is the data structure that matches exactly. It maintains a collection of disjoint sets and supports two operations: find(x) returns the identifier of the set containing x, and union(x, y) merges the sets containing x and y into one. Both operations run in O(α(n)) time, where α is the inverse Ackermann function — effectively constant for any realistic input. With path compression and union-by-rank, you can think of Union-Find as "constant-time group operations" without losing much in practice.
The algorithm becomes: when a cell flips to land, create a new singleton set for it and increment the island count. Then for each of its four neighbors that's also land, call union between this cell and that neighbor — and if the union actually merged two distinct sets, decrement the count. After all four neighbors are processed, the count reflects the new state. Each update is O(α(n)) per neighbor check, so essentially O(1) per update — a massive improvement over re-running DFS on the whole grid.
You wouldn't lead with Union-Find for the basic problem — DFS is genuinely simpler when the grid is static. But knowing it lets you handle dynamic-update follow-ups intelligently, and it shows the interviewer that you can choose the right data structure based on the operations a problem actually requires.
5. Discuss Trade-Offs Between Solutions
Approach | Time | Space | When I'd use it |
Brute force with separate visited matrix | O(m × n) | O(m × n) | If modifying the input is forbidden |
DFS with in-place marking | O(m × n) | O(m × n) stack | My default interview answer — clean and memory-efficient |
BFS with queue | O(m × n) | O(min(m, n)) average, O(m × n) worst | If the grid is large and stack overflow is a real concern |
Union-Find | O(m × n × α(m × n)) | O(m × n) | Overkill for the basic problem, but powerful if the input is streamed or if you need to support dynamic updates |
6. Pseudocode
numIslands(grid):
if grid is empty: return 0
count = 0
for r in 0..rows-1:
for c in 0..cols-1:
if grid[r][c] == '1':
count++
dfs(grid, r, c)
return count
dfs(grid, 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' # mark visited BEFORE recursing
dfs(grid, r - 1, c)
dfs(grid, r + 1, c)
dfs(grid, r, c - 1)
dfs(grid, r, c + 1)7. Edge Cases
Things to verify before claiming we're done:
Empty grid → early return 0. ✓
Grid with all '0' → outer scan finds no land, count stays 0. ✓
Grid with all '1' → entire grid is one island; the first DFS sinks everything; count = 1. ✓
Single-cell grid → either 0 or 1 depending on the cell's value.
Long snake-shaped island → recursive DFS depth could equal m × n. For very large inputs, BFS is safer.
Disconnected islands of different sizes and shapes → standard case the algorithm handles directly.
Islands touching the grid border → the bounds check in DFS prevents out-of-range access.
The bounds check at the top of dfs is what handles all the edge cells uniformly — without it, accessing grid[r-1][c] for r = 0 would crash. Putting the bounds check before the value check is what makes the recursive calls safe.
8. Full Code
public class NumberOfIslands {
public static int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
// Found an unvisited land cell —
// start of a new island
islands++;
dfs(grid, r, c);
}
}
}
return islands;
}
private static void dfs(char[][] grid, int r, int c) {
// Bounds check FIRST so the value check below is safe
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) {
return;
}
// Water or already-visited land — stop exploring
if (grid[r][c] == '0') {
return;
}
// Mark BEFORE recursing to break the cycle that would
// otherwise bounce back and forth between adjacent cells
grid[r][c] = '0';
dfs(grid, r - 1, c); // up
dfs(grid, r + 1, c); // down
dfs(grid, r, c - 1); // left
dfs(grid, r, c + 1); // right
}
// BFS alternative — safer for very large grids where recursion
// depth could be a problem. Same O(m × n) time and space.
public static int numIslandsBFS(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
islands++;
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{r, c});
grid[r][c] = '0'; // mark on enqueue, not on dequeue
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : directions) {
int nr = cell[0] + d[0];
int nc = cell[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& grid[nr][nc] == '1') {
grid[nr][nc] = '0';
queue.offer(new int[]{nr, nc});
}
}
}
}
}
}
return islands;
}
}Note in the BFS version that we mark cells on enqueue, not on dequeue. If we marked on dequeue, the same cell could be added to the queue multiple times before being processed (once for each adjacent cell that sees it as unvisited). Marking on enqueue ensures each cell enters the queue at most once.
9. Test the Code
char[][] grid1 = {
{'1','1','0','0','0'},
{'1','1','0','0','0'},
{'0','0','1','0','0'},
{'0','0','0','1','1'}
};
System.out.println(numIslands(grid1)); // 3
// Single cell of water
char[][] grid2 = {{'0'}};
System.out.println(numIslands(grid2)); // 0
// Single cell of land
char[][] grid3 = {{'1'}};
System.out.println(numIslands(grid3)); // 1
// All water
char[][] grid4 = {
{'0','0','0'},
{'0','0','0'},
{'0','0','0'}
};
System.out.println(numIslands(grid4)); // 0
// All land — one big island
char[][] grid5 = {
{'1','1','1'},
{'1','1','1'},
{'1','1','1'}
};
System.out.println(numIslands(grid5)); // 1
// Diagonal cells — should NOT count as one island
char[][] grid6 = {
{'1','0','1'},
{'0','1','0'},
{'1','0','1'}
};
System.out.println(numIslands(grid6)); // 5 (diagonals don't connect)
// Long snake-shaped island
char[][] grid7 = {
{'1','1','1','1','1'},
{'0','0','0','0','1'},
{'1','1','1','1','1'},
{'1','0','0','0','0'},
{'1','1','1','1','1'}
};
System.out.println(numIslands(grid7)); // 1These hit the meaningful cases: a normal case with multiple islands, single-cell grids in both directions, all-water and all-land, the diagonal trap (which catches algorithms that wrongly include diagonal adjacency), and a snake-shaped island that stresses recursion depth.
10. Key Lessons
When a problem is presented as a grid, ask whether it's actually a graph in disguise. Grids with adjacency-based connectivity rules are graphs; the cells are nodes, and the adjacency rule defines the edges. Recognizing this reframing unlocks a whole family of standard techniques (DFS, BFS, Union-Find) that would be hard to invent from scratch on a grid.
When marking visited nodes during traversal, mark before recursing into neighbors, not after. The marking is what breaks the cycle that would otherwise cause infinite recursion or duplicate processing.
For graph problems on grids, you almost never need to build an explicit adjacency list. The grid itself encodes adjacency through coordinate arithmetic — neighbors of (r, c) are computed on the fly. Building an explicit graph is wasted memory.
In-place modification of the input is often the cleanest way to track "visited" state. It removes the need for a separate matrix and keeps the code shorter. Just check whether modification is allowed before doing it.
DFS and BFS are interchangeable for connected-components problems. Pick DFS for code clarity; pick BFS when recursion depth could be a problem. Mention both in interviews to show you understand the trade-off.
The thing that makes Number of Islands click isn't DFS or BFS — both are standard techniques you already know. It's the cognitive move of looking at a 2D grid and seeing a graph underneath. Once you train yourself to ask "what's the underlying structure?" instead of treating each problem's surface presentation as the structure, you'll find that dozens of seemingly different problems share the same handful of algorithms. The hard part isn't the algorithm — it's the recognition.
Good Luck and Happy Coding!
Comments