In this article
Before you start
This page is one pattern in the coding interview patterns and method learning path.
Why interviewers ask this
Number of islands tests whether a candidate can see that a picture is a graph, choose a traversal, and keep the counting job apart from the marking job. NeetCode lists Array, Depth-First Search, Breadth-First Search, Union Find and Matrix as the topics of this problem, so one question touches several skills. Step 3 defines depth-first and breadth-first search, and the trade-offs section defines Union-Find.
A weak answer codes a recursive function and returns its call count, or lets diagonal cells connect. A strong answer states the neighbor rule first, puts the counter in the outer loop, and explains why each cell is handled a constant number of times. A Staff-level answer adds what breaks: the recursion limit on one huge island, the cost of changing the input, and where Union-Find fits when land arrives over time.
Number of islands from first principles
- Island
- An island is a maximal group of land cells in a grid where every cell can be reached from every other by moving up, down, left or right over land only, and no further land cell touches the group horizontally or vertically. Diagonal contact does not join cells, and water cells never belong to an island.
- Connected component
- A connected component is a maximal set of nodes in a graph in which every node can reach every other along links, so no link leads out of the set. Counting islands is counting the connected components formed by land cells, where each land cell links to its four horizontal and vertical neighbors.
- Flood fill
- Flood fill is a traversal that starts at one cell and visits every cell connected to it, marking each as visited, so the whole region is consumed in one pass. In this problem it runs once per island and uses depth-first or breadth-first search to spread.
In plain words
Picture a map of ponds seen from above. You walk across it row by row. Each time you reach a pond you have not seen, you pour dye in it and the dye fills that pond completely. You count one pour per pond. A pond that already holds dye is skipped. The number of pours is the number of ponds.
The analogy breaks in one place. Real dye also creeps across a corner. In this problem the dye moves only up, down, left and right.
The statement from NeetCode reads: given a grid where "1" is land and "0" is water, count the islands. An island joins adjacent land horizontally or vertically, and the edges of the grid are assumed to be water. In one precise sentence, the answer is the number of connected components of land cells under four-neighbor adjacency (Hello Interview community page).
Step 1: Land cells connect only to their four neighbors
Only up, down, left and right neighbors connect land cells. A cell at row r and column c can join the cells at r plus or minus one in the same column and at c plus or minus one in the same row. A land cell touching another only at a corner is not joined to it, and the community statement lists that case as an edge case.
Input: a grid of land and water. Output: an implied graph in which each land cell has at most four links. You do not build that graph in memory. The grid already is the graph, and a small loop over four direction offsets lists the neighbors of any cell. You now know what "connected" means, which is all the next step needs.
Step 2: The outer scan counts and the flood fill only marks
The outer scan adds one to the count for each unvisited land cell. The loop reads every cell in row order. On land that is not yet visited, it adds one to the counter and starts a flood fill. The rule comes from graph theory: a traversal must be started at least once for each connected component. The loop over every cell is this page's way of doing that: it starts the fill on each land cell that is still unvisited. The count lives in the outer scan and the consumption in the fill. As the community statement puts it, "Only after fully exploring one island do we continue searching for the next one."
That split is why counting recursive calls is wrong. A fill makes many calls for one island, but it was started once. On the worked grid below, a version that calls its helper on every neighbor makes 31 calls and the answer is 3.1 Count the starts, never the calls.
Step 3: The flood fill marks the whole island with a stack or a queue
Flood fill marks every land cell of that island as visited. It can use depth-first search or breadth-first search (algoviz). Depth-first search (DFS) is a traversal that follows one path as far as it can and then backs up, using recursion or a stack. Breadth-first search (BFS) is a traversal that visits all neighbors of a cell before going further, using a queue. Both give the same answer and the same time complexity.
Input: the start cell. Each step takes one cell from the stack or queue, looks at its four neighbors, and for every neighbor that is land and unvisited, marks it and adds it to the stack or queue. Output: every cell of the island marked. Mark a cell when you add it, not when you take it out, so no cell is added twice. The stack and the queue are the same idea as in monotonic stack, used for a different job.
Step 4: Visited cells are skipped, so each cell costs constant work
Visited cells are skipped, so each cell costs a constant amount of work. Each cell is read once by the scan and expanded at most once by a fill, so time is linear in the grid size, written O(m·n) for m rows and n columns. A fill never revisits a marked cell, which is why the total is not quadratic.
Space is O(m·n) in the worst case, because a grid that is one giant island can fill the stack or queue with a large share of its cells (algoviz). One community page quotes a limit of 300 for m and n, and then the largest grid has 90,000 cells.1 NeetCode's own constraint is 100, so check the limit in the statement you are given.
Step-by-step description
- Land joins only up, down, left and right.
- Each unvisited land cell adds one.
- The fill marks the whole island.
- Marked cells cost constant work.
- Only up, down, left and right neighbors connect land cells.
- The outer scan adds one to the count for each unvisited land cell.
- Flood fill marks every land cell of that island as visited.
- Visited cells are skipped, so each cell costs a constant amount of work.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
Take this grid of four rows and five columns, a standard example whose answer is 3 (Hello Interview community page describes the same shape). Rows and columns are counted from zero.
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1The scan reads row 0 and meets land at row 0, column 0. The count becomes one and the fill marks the two-by-two block. The scan then passes three land cells that are already marked and skips them: row 0 column 1, row 1 column 0 and row 1 column 1. At row 2, column 2 it finds a lone cell. That cell touches the block only at a corner, so the count becomes two. At row 3, column 3 it finds the last island, the fill marks row 3, column 4, and the count becomes three.1
The grid has seven land cells. The two-by-two block has four cells, the single cell has one and the right-hand pair has two.1
| Quantity | Value (computed) |
|---|---|
| Cells in the grid | 20 1 |
| Land cells | 7 1 |
| Islands found | 3 1 |
| Island sizes in scan order | 4, 1 and 2 cells 1 |
| Cells read by the outer scan | 20 1 |
| Land cells skipped as already marked | 4 1 |
| Cells expanded by flood fills | 7 1 |
| Neighbor checks in total | 28 1 |
| Helper calls if every neighbor is a call | 31 1 |
| Islands if diagonals also connect | 1 1 |
| Cells in a 300 by 300 grid | 90,000 1 |
Step-by-step description
- The scan meets land at row 0, column 0; the count becomes one and the fill marks the two-by-two block.
- The scan passes three land cells that are already marked and skips them.
- At row 2, column 2 it finds a lone cell that touches the block only at a corner, so the count becomes two.
- At row 3, column 3 it finds the last island, the fill marks row 3, column 4, and the count becomes three.
- The count becomes one and the fill marks the two-by-two block.
- At row 2, column 2 it finds a lone cell that touches the block only at a corner, so the count becomes two.
Here is a Python version. It uses an explicit stack and a visited set, so it does not change the input and cannot hit the recursion limit.
def num_islands(grid):
if not grid: # an empty grid has no islands
return 0
rows, cols = len(grid), len(grid[0])
seen = set()
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in seen:
count += 1 # the count lives here
seen.add((r, c))
stack = [(r, c)]
while stack: # the fill only marks
y, x = stack.pop()
for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ny, nx = y + dy, x + dx
if (0 <= ny < rows and 0 <= nx < cols
and grid[ny][nx] == "1"
and (ny, nx) not in seen):
seen.add((ny, nx))
stack.append((ny, nx))
return countThe counter changes in one place, the outer loop. The inner loop only fills seen. The same algorithm was run on the worked grid in the data script.1
Trade-offs and edge cases
Every approach to number of islands counts the same components. They differ in what can go wrong. Recursive depth-first search is short to write, and the same recursive walk searches a tree in lowest common ancestor of a binary tree. On one large island, though, it can pass Python's recursion limit, which is the maximum depth of the interpreter stack, and the fix is an explicit stack or breadth-first search. For more Python background, see Python interview questions.
Union-Find is a structure that keeps groups of items and answers "are these two in the same group" with a find operation and a merge with a union operation. Each land cell starts as its own group, and each pair of adjacent land cells is merged. On the worked grid there are 5 adjacent land pairs, 4 of them merge two different groups, and the 7 starting groups fall to 3.1
With path compression and union by size or rank, any sequence of m operations on n elements costs O(m·α(n)) in the worst case, an almost-constant amortized cost per operation, where α is the inverse of a very fast-growing function (Gelle and Iván, arXiv 1510.07462v2, 2017). Union-Find suits the follow-up where land is added over time.
| Approach | Time | Extra space | Main risk |
|---|---|---|---|
| Recursive DFS | linear in cells | call stack, up to all cells | Python recursion limit |
| Stack or BFS | linear in cells | stack or queue, up to all cells | more code than recursion |
| Union-Find | near linear | parent array, one entry per cell | more code to write |
Text description of the diagram
- Recursive depth-first search can pass Python's recursion limit on one large island.
- Union-Find suits the follow-up where land is added over time.
Edge cases follow. Marking visited cells by sinking land to water avoids a separate set, as NeetCode's hint describes ("we mark the visited 1's as 0 to ensure we don't revisit them"), but it modifies the input, so ask whether that is acceptable first; a visited set costs O(m·n) and changes nothing else.
Space is not O(1) even when you mutate the grid, because the stack or queue can still grow with the island. An all-water grid has no islands, an all-land grid has one, and an empty grid has none, which the code above checks first. A different problem, detecting a cycle in a directed graph, needs more than visited and unvisited marks, since one mark cannot tell a finished branch from an active one.
How to answer it in an interview
How would you count the islands in a grid of land and water?
I treat the grid as a graph where each land cell links to its four horizontal and vertical neighbors, so an island is a connected component. I scan every cell. When I find land I have not visited, I add one to the count and run a flood fill, with a stack or a queue, that marks the whole island. Each cell is scanned once and expanded at most once, so time is O(m·n), and space is O(m·n) in the worst case. In Python I use an explicit stack, because one large island can pass the recursion limit. If I may change the input, I sink land to water instead of keeping a visited set.
The spoken structure: say the grid is a graph, say the count sits in the scan, say what the fill does, then give time, space and the recursion warning.
Common mistakes
- "The answer is the number of DFS calls." (wrong) A fill makes many calls for one island. (right) "The answer is the number of times the scan starts a fill."
- "Diagonal cells connect." (wrong) Connectivity is horizontal and vertical only. (right) "Four-direction adjacency; if diagonals should count, the worked grid would change from three islands to one."1
- "The fill runs for every cell, so the cost is quadratic." (wrong) A marked cell is never expanded again. (right) "Each cell is scanned once and expanded at most once, so the cost is linear in the grid size."
- "Union-Find is constant time per operation." (wrong) It is near-constant, not constant. (right) "Per operation it is amortized O(α(n)) with path compression and union by size or rank: near-constant but not O(1), and one find can cost more."
- "Recursion is always fine." (wrong) One big island can pass the default limit. (right) "I use an explicit stack or breadth-first search for large grids."
Follow-up questions
What is the time and space complexity of number of islands?
Time is O(m·n), because the scan reads each cell once and a fill expands each land cell at most once. Space is O(m·n) in the worst case, from the stack, the queue or the visited set.
Does BFS or DFS work better for number of islands?
Neither wins on complexity: both visit each land cell once and give the same count. Pick depth-first search for short code, or breadth-first search or an explicit stack to avoid the recursion limit on a large single island.
How do you count islands when land is added one cell at a time?
Use Union-Find. Start each new land cell as its own group, merge it with any land neighbors, and keep a running count. The rule is: add one when a new land cell arrives, subtract one for every merge of two different groups, and ignore a cell that is already land. This avoids rescanning the whole grid after each change.
Is the NeetCode version of number of islands a different problem?
No, it is the same problem. The NeetCode statement uses the same land, water and four-direction rules, but it lists a limit of 100 for the grid sides, while a community page quotes 300 for the original, so read the limits you are given.
How do you count islands without changing the input grid?
Keep a set of visited coordinates and mark cells there, as in the code above. It costs O(m·n) extra space and nothing else changes. Sinking land to water saves that set but needs the interviewer's agreement to modify the input.
What if diagonal cells should connect?
Add the four diagonal offsets to the direction list, for eight directions in all. Nothing else in the algorithm changes. On the worked grid the answer changes from three to one, because the corner contacts join all three islands.1 A sibling variant, max area of island, uses the same fill and keeps the largest size; on the worked grid the sizes are 4, 1 and 2, so the largest is 4.1
- Number of islands counts connected components of land cells under four-direction adjacency.
- The count lives in the outer scan; the flood fill only marks the island as visited.
- Depth-first and breadth-first fills both give linear time, O(m·n), and worst-case space O(m·n).
- Use an explicit stack or breadth-first search when one island could pass Python's recursion limit.
- Union-Find gives the same count and suits the follow-up where land is added over time.
Sources
- Recognizing Union-Find trees is NP-complete (arXiv 1510.07462), background section — arXiv, 5 Jan 2017
- Graph traversal — Wikipedia, 26 Oct 2026
- Number of Islands (problem page) — NeetCode, 26 Oct 2026
- Number of Islands (statement, examples, constraints) — Hello Interview community, 26 Oct 2026
- Island Count: Connected Components in a 2D Grid — algoviz, 26 Oct 2026
- sys.setrecursionlimit (Python standard library documentation) — Python Software Foundation, 26 Oct 2026
