Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Treat the grid as a graph where adjacent land cells ('1') are connected. Scan every cell; when you hit unvisited land, run a flood fill (DFS or BFS) that sinks the entire connected island, then increment a counter. Each cell is visited once → O(rows × cols) time. Union-Find is an alternative when islands merge dynamically.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise a grid as an implicit graph and count connected components with flood fill, and whether you correctly mark cells visited so nothing is double-counted.
Where candidates slip
Forgetting to mark cells visited (infinite recursion / re-counting), going out of bounds, or counting each land cell instead of each connected component.
How to stand out
State the grid-as-graph framing, give both DFS and BFS (and why BFS avoids stack overflow), mention Union-Find for dynamic connectivity, and note the in-place 'sink the island' trick saves the visited set.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount connected land regionsEdges added incrementally?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
DFS Flood Fill
1Hint 1Explore hintHide hint
Think of the grid as a graph: each land cell is a node connected to its 4 land neighbours. How do you count connected components of a graph?
2Hint 2Explore hintHide hint
Scan every cell. The first time you touch an unvisited land cell, that's a brand-new island — bump the counter.
3Hint 3Explore hintHide hint
Then 'sink' the entire island so you never count it again: recursively turn this cell and all connected land into water (or mark visited), exploring the 4 neighbours.
A · Core idea
Frame the grid as an implicit graph and count its connected components.
Outer scan = component discovery. Walk every cell. When you encounter land that hasn't been claimed yet, you've found the seed of a new island, so increment the count. The key is that you only count at the seed — the flood fill then absorbs the rest of that island so its other cells never trigger another count.
Flood fill = sink the component. From the seed, recurse to the 4 orthogonal neighbours, sinking each land cell to water ('1' → '0') as you go. Sinking doubles as the visited marker: a cell that's already water is ignored, which is exactly the base case that stops recursion. The recursion naturally traces the whole connected blob.
Why sinking in place is elegant. Instead of a separate visited[][] matrix, mutating the grid records progress for free. State up front that this mutates the input; if the caller needs the grid intact, use a visited set instead.
Base cases that keep it correct. The recursion returns immediately when (a) the index is out of bounds, or (b) the cell is water. Those two checks prevent both array-index errors and infinite loops, and they're the only guards you need.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
grid = [[1,1,0],[1,0,0],[0,0,1]]Live grid state
Cells change as the traversal moves
(0,0)='1'new island → count=1; DFS sinks (0,0),(0,1),(1,0)
2C · Code with teaching comments
Reference implementation previewpublic int numIslands(char[][] grid) { int count = 0; for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[0].length; c++) { if (grid[r][c] == '1') {Explore the full codeHide the full code
D · Why it works and complexityO(m × n) timeO(m × n) worst-case recursion stack spaceOpen the invariant and proofExplore the proofHide the proof
Counting islands is counting connected components, and the increment happens exactly once per component — at the first cell the outer loop reaches. The flood fill's job isn't to count; it's to erase the component so the outer loop's counter stays honest.
ComplexityO(m × n) time, O(m × n) worst-case recursion stack space — Every cell is examined a constant number of times: once by the outer scan and once when sunk by a flood fill. So O(m × n). The recursion depth can reach the size of one island, up to O(m × n) in the worst case (a grid that's all land).
E · Edge cases and pitfalls7all water — No cell triggers a count; returns 0.Explore edge casesHide edge cases
Edge cases handled
all waterNo cell triggers a count; returns 0.single cell '1'One island; DFS sinks the lone cell; returns 1.entire grid landFirst cell seeds one island; DFS sinks everything; returns 1 (recursion depth ~ m×n).
Pitfalls
- Not sinking/marking visited — causes infinite recursion and/or massive over-counting.
- Counting every land cell instead of once per connected component.
- Including diagonal neighbours when the problem only connects orthogonally.
- Deep recursion on a 300×300 all-land grid can overflow the stack — prefer BFS there.
Approach 2 of 2 · Optimal
BFS Flood Fill
1Hint 1Explore hintHide hint
Same idea as DFS, but explore the island level by level using an explicit queue instead of recursion.
2Hint 2Explore hintHide hint
When you find new land, mark it visited, enqueue it, and then repeatedly dequeue a cell and enqueue its unvisited land neighbours.
3Hint 3Explore hintHide hint
Mark cells visited at ENQUEUE time, not dequeue time, so a cell is never added to the queue twice.
A · Core idea
Identical strategy to DFS — count once per component, then consume the component — but the traversal is iterative.
Why iterative matters. A recursive DFS on a fully-land 300×300 grid can recurse ~90,000 deep and blow the call stack in languages with modest stack limits. BFS moves that frontier into a heap-allocated queue, which scales to any grid size without stack risk.
Mark visited at enqueue, not dequeue. The single most important BFS detail: the moment you put a cell on the queue, sink it (or mark visited). If you wait until you dequeue it, the same cell can be enqueued multiple times by different neighbours, inflating the queue and re-processing cells. Enqueue-time marking guarantees each cell is touched once.
Frontier expansion. Pop a cell, look at its 4 neighbours, and enqueue every neighbour that's in-bounds and still land. The island is exhausted when the queue empties; then the outer scan continues looking for the next seed.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
grid = [[1,1,0],[1,0,0],[0,0,1]]Live grid state
Cells change as the traversal moves
(0,0)='1'count=1; enqueue (0,0), sink
2C · Code with teaching comments
D · Why it works and complexityO(m × n) timeO(min(m, n)) typical queue size spaceOpen the invariant and proofExplore the proofHide the proof
DFS and BFS here are interchangeable for counting — both just need to fully consume each component. BFS is the safer default at scale because its memory is the frontier size, not the recursion depth, which can be far smaller and never risks a stack overflow.
ComplexityO(m × n) time, O(min(m, n)) typical queue size space — Each cell enters and leaves the queue at most once → O(m × n). The queue holds at most a 'frontier' of the island; for a grid that's O(min(m, n)) in the typical worst case (a diagonal frontier).
E · Edge cases and pitfalls6long thin all-land grid — BFS handles it iteratively with a small frontier; DFS might recurse very deep.Explore edge casesHide edge cases
Edge cases handled
long thin all-land gridBFS handles it iteratively with a small frontier; DFS might recurse very deep.single row [1,0,1,0,1]Three isolated land cells → 3 islands.all waterQueue never starts; returns 0.
Pitfalls
- Marking visited at dequeue time — the same cell gets enqueued by multiple neighbours, blowing up the queue.
- Using an ArrayList/list as a queue with removal from the front — O(n) per pop; use a deque/LinkedList.
- Forgetting bounds checks before reading grid[nr][nc].
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int numIslands(char[][] grid) { int rows = grid.length, cols = grid[0].length, count = 0; int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Forgetting to mark visited
Without sinking the cell (or a visited set), neighbours keep re-entering the same land, causing infinite recursion/looping and counting one island many times.
Explore the code comparisonHide the code comparison
Forgetting to mark visited
Without sinking the cell (or a visited set), neighbours keep re-entering the same land, causing infinite recursion/looping and counting one island many times.
Don't write this
def dfs(r, c):
if not in_bounds(r, c) or grid[r][c] != '1':
return
# forgot to mark visited
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)Write this instead
def dfs(r, c):
if not in_bounds(r, c) or grid[r][c] != '1':
return
grid[r][c] = '0' # sink before recursing
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)2Counting cells instead of components
Incrementing the counter inside the flood fill (per land cell) reports the number of land cells, not islands. The count must happen once per seed, in the outer scan.
Explore the code comparisonHide the code comparison
Counting cells instead of components
Incrementing the counter inside the flood fill (per land cell) reports the number of land cells, not islands. The count must happen once per seed, in the outer scan.
Don't write this
private void dfs(char[][] g, int r, int c) {
if (out(r,c) || g[r][c] != '1') return;
count++; // wrong: counts every land cell
g[r][c] = '0';
// ...recurse
}Write this instead
// count once in the scan, before flood-filling
if (grid[r][c] == '1') {
count++;
dfs(grid, r, c); // dfs only sinks, never counts
}Revise
Carry the pattern into the interview
Pattern to remember
Connected-components on a grid via flood fill (DFS/BFS)
Code pattern to memorize
count = 0
for each cell (r, c):
if grid[r][c] == '1':
count += 1
flood_fill(r, c) # sink this whole island
return count
flood_fill sinks '1'→'0' and recurses/queues 4 neighbours.Rules to remember
- 1Each new unvisited land cell starts one island; the flood fill consumes the rest of it so it isn't recounted.
- 2Mark visited by sinking the cell ('1' → '0') or using a separate visited set — never revisit, or you'll loop forever / over-count.
- 3Explore exactly 4 directions (up/down/left/right) unless the problem says diagonals connect.
- 4DFS is simplest to write (recursion); BFS (queue) avoids deep-recursion stack overflow on huge grids.
- 5Bounds-check before recursing:
0 ≤ r < rowsand0 ≤ c < cols.
Use this pattern when
- Counting connected regions / blobs in a grid or matrix
- 'Flood fill', region-coloring, or area-of-connected-cells problems
- Any implicit graph where neighbours are grid-adjacency
- Detecting reachable clusters from arbitrary starting cells
Choose another pattern when
- Edges added incrementally and you must re-query connectivity → Union-Find shines
- You need shortest distance between cells → BFS specifically (not DFS)
- Weighted movement costs → Dijkstra, not plain flood fill
Interview takeaway
Number of Islands is the canonical grid-as-graph problem: every cell is a node, adjacency is the edge, and counting islands is counting connected components. Master the flood-fill template (DFS or BFS) and you've unlocked Max Area of Island, Surrounded Regions, Pacific Atlantic, and Rotting Oranges.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternGrid-as-graph connected components via flood fill (DFS/BFS). The foundational matrix-traversal pattern; Union-Find handles dynamic edge additions. Same family as Max Area of Island, Surrounded Regions, Pacific Atlantic Water Flow, and Rotting Oranges.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Max Area of IslandComing soonSame flood fill, but return the size of each component and track the maximum.
- Surrounded RegionsFlood fill from the borders to mark safe regions, then flip the rest.
- Number of Islands IIComing soonLand added one cell at a time → Union-Find with a running component count.
- Number of Closed IslandsComing soonExclude islands touching the border (flood those first), then count the rest.