Problem and When It Applies
Given an m × n grid containing only "1" for land and "0" for water, return the number of islands. Two land cells are connected only when they share a horizontal or vertical edge. An island is a maximal connected set of land cells.
The constraints are 1 <= m, n <= 300. The implementation still defends against an empty array instead of turning a caller contract into a runtime failure. Assume the grid may be modified. If the caller must retain it, use a same-sized visited matrix instead.
This is a general algorithms question for software engineering coding rounds. It tests whether a candidate can model a matrix as an implicit graph, traverse connected components, and keep the implementation consistent with the complexity analysis.
What the Interviewer Evaluates
A strong answer treats each land cell as a vertex and each four-direction land adjacency as an edge. That produces the key rule: whenever the scan reaches unvisited land, it has found a new connected component. Count it once, then traverse and mark the entire island so it cannot be counted again.
Implementation details matter. Mark a neighbor when it is pushed, not when it is popped; otherwise multiple adjacent cells can push the same cell. Iterative DFS avoids a deep language call stack when most of the grid is one island. A precise answer also says that in-place marking removes the visited matrix, while the explicit stack can still occupy O(mn) space in the worst case.
A weak answer merely says “use DFS” without defining connectivity, the input mutation, a correctness invariant, or adversarial tests.
Questions to Clarify First
- Do diagonals connect? This problem uses four directions. If eight directions count, extend the direction list and expect some answers to change.
- May the input be modified? If yes, turn visited
"1"cells into"0". Otherwise usevisited, preserving the time bound while adding O(mn) storage. - Is the grid rectangular and nonempty? The prompt guarantees both; production code can still return 0 for an empty input. A jagged array would require bounds based on each row.
- Is this one static count or a count after every land insertion? DFS or BFS fits the static grid. Incremental insertions favor disjoint set union.
- What are the size and call-stack limits? A 300×300 all-land grid can induce a path with 90,000 recursive calls, so this solution uses an explicit stack.
30-Second Answer Framework
“I will model land cells as vertices in an implicit graph, with four-direction adjacency as edges. I scan the grid row by row. Every remaining 1 starts an unprocessed connected component, so I increment the island count and run iterative DFS from it. I turn a land neighbor into 0 when pushing it, which prevents duplicate pushes. Each cell is pushed at most once, and an explicit stack avoids deep recursion. The time complexity is O(mn), and the stack is O(mn) in the worst case. If mutation is forbidden, I will store the same state in a visited matrix.”
Step-by-Step Deep Dive
Step 1: Find the repeated work in a naive search
Starting a fresh search from every land cell would traverse the same island many times. Finding neighbors is not the bottleneck; the missing piece is state that persists across searches and records that a cell already belongs to a counted component.
A full scan plus permanent visitation marks removes that repetition. Start a traversal only from land that remains unvisited.
Step 2: Establish the counting invariant
When the scan reaches (r, c), every previous DFS has marked exactly one complete island. If the current cell is still "1", none of those traversals reached it, so it must start a new island and the count increases by one.
The DFS follows only four-direction land edges, so it cannot cross water and merge distinct islands. It also reaches every land cell connected to its start, so this island cannot trigger another count later. Those two facts prove both no undercounting and no double counting.
Step 3: Mark when pushing
Suppose an unmarked cell touches two cells already in the stack. If marking waits until pop time, both neighbors can push that cell. The result is often still correct, but the stack contains duplicate work and the tight complexity argument is lost.
Change a discovered neighbor to "0" before pushing it. Any later edge will then see it as visited, guaranteeing that each land cell enters the stack at most once.
Step 4: Implement iterative DFS
function numIslands(grid) {
if (grid.length === 0 || grid[0].length === 0) return 0;
const rows = grid.length;
const cols = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let islands = 0;
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] !== "1") continue;
islands += 1;
grid[row][col] = "0";
const stack = [[row, col]];
while (stack.length > 0) {
const [currentRow, currentCol] = stack.pop();
for (const [rowOffset, colOffset] of directions) {
const nextRow = currentRow + rowOffset;
const nextCol = currentCol + colOffset;
if (
nextRow >= 0 && nextRow < rows &&
nextCol >= 0 && nextCol < cols &&
grid[nextRow][nextCol] === "1"
) {
grid[nextRow][nextCol] = "0";
stack.push([nextRow, nextCol]);
}
}
}
}
}
return islands;
}The scan inspects mn cells. Every land cell is pushed at most once and checks four neighbors, so the time is O(mn). The explicit stack can hold O(mn) coordinates on an all-land grid. The function mutates its input. Copying the grid instead also costs O(mn) time and space.
Step 5: Validate boundaries and adversarial cases
At minimum, test: an empty array returns 0; one water cell returns 0; one land cell returns 1; all water returns 0; all land returns 1; two cells touching only diagonally return 2; the sample with three separated regions returns 3; and a 300×300 all-land grid does not overflow a recursive call stack.
Also test the mutation contract. If another assertion needs the original grid after the call, copy it first or use visited. This choice belongs in the interface contract, not as a hidden implementation detail.
Step 6: Compare alternatives
BFS and iterative DFS have the same time and worst-case space here. Choose BFS when distance layers matter; either is appropriate when the only goal is to exhaust a component. Recursive DFS is shorter only when the input is small enough or the language guarantees sufficient depth. Disjoint set union is useful when land arrives incrementally and the count is requested after each insertion; it adds needless indexing and set maintenance for one static count.
High-Quality Sample Answer
“This problem is connected-component counting in an implicit undirected graph. Every 1 is a vertex, and horizontal or vertical land neighbors share an edge. I scan the whole grid. If a position is still 1, no earlier search reached it, so I have found a new island and increment the count. I then run iterative DFS and turn that whole island into 0.
I mark neighbors when pushing them so two adjacent cells cannot push the same position. I use an explicit stack because a 300×300 all-land grid may produce a very deep recursive path. Each cell is processed at most once and checks four directions, giving O(mn) time and O(mn) worst-case stack space. This version mutates the input; if the interface must preserve it, I will move the marks into an O(mn) visited matrix. I would verify diagonal non-connectivity, all-water, all-land, and empty-input boundaries.”
This answer connects the model, the counting argument, implementation risk, side effect, and validation without relying on a memorized label.
Common Mistakes
- Treat diagonals as connected → this changes the problem and may undercount islands → keep only up, down, left, and right in the direction list.
- Mark only when popping → multiple neighbors may push the same cell → mark a valid neighbor immediately before pushing.
- Claim in-place means O(1) space → this ignores the worst-case explicit stack → report O(mn) auxiliary space in the worst case.
- Use recursive DFS without discussing depth → one large island can exhaust the language call stack → use iteration or establish a safe size bound.
- Mutate caller data silently → later code observes a cleared grid → document the side effect or use
visited. - Search again from every land cell → the same component is traversed repeatedly → start only from unvisited land.
- Test only ordinary rectangles → empty, all-water, all-land, and diagonal counterexamples remain untested → cover minimal, extreme, and adversarial cases.
Follow-Up Questions and Responses
Follow-up 1: What if the input cannot be modified?
Allocate an m × n Boolean matrix and mark a location visited when pushing it. The counting invariant and O(mn) time remain unchanged; additional storage is explicitly O(mn). Copying the input has the same asymptotic space cost but different semantics.
Follow-up 2: What if diagonals also connect?
Expand the direction list from four offsets to eight; the traversal framework is unchanged. First confirm the rule with a case such as [[1, 0], [0, 1]]: the four-direction answer is 2, while the eight-direction answer is 1.
Follow-up 3: What if land is added one cell at a time and every count is requested?
Repeating static DFS wastes work. Use disjoint set union instead: a new land cell initially increments the count, then unions with every existing land neighbor. Each successful union of two different sets decrements the count. Duplicate insertions must be ignored so they do not increment twice.
Follow-up 4: What if the coordinate range is huge but land is sparse?
Do not allocate the full matrix. Store only land coordinates in a hash set, traverse those coordinates, and probe four neighbors. With k land cells, expected time is O(k), and the visited set plus stack is O(k). This conclusion requires a sparse coordinate-list representation; it does not follow from a dense grid input.