In this article
Before you start
This page is one step of the coding interview patterns and method learning path.
Why interviewers ask this
A wrong tool on a grid costs the whole round: a depth-first search returns a path, not the shortest path, and a search used to count paths runs far too long. Grid questions are a compact way to see whether a candidate sorts a problem by its answer type before writing code.
Candidates report grid prompts such as the shortest path between two points, the time for something to spread to every cell, and finding disconnected regions and then counting paths past obstacles. These are reported by candidates, not confirmed by a public source.
A weak answer reaches for recursion on every grid. A strong answer names the question type, picks the matching rung, and states the visit rule and the cost. A Staff-level answer adds the failure modes: duplicate queue entries, recursion depth on big grids, and the point where search stops being the right tool.
Grid BFS/DFS ladder from first principles
- Multi-source BFS
- Multi-source BFS is a breadth-first search that puts every starting cell into the queue before the first step, so all sources spread outward together and each cell is reached at its distance from the nearest source. It is one search, not one search per source.
- Visited set
- A visited set is the record of cells the search has already claimed, so no cell is processed twice and the search cannot loop forever. On a grid it is a separate boolean table, a set of coordinates, or a marker written into the grid itself, which saves memory but destroys the input.
In plain words
Picture a drop of ink on wet paper. It spreads outward in rings. Each ring is one step further from the drop. Breadth-first search does the same thing on a grid. The analogy breaks in one place. Ink never returns to a spot it has soaked. Code does, unless a visited set stops it.
Depth-first search is different. It is like walking a maze with one hand on the wall. You go as far as you can. Then you back up.
In one precise sentence, the ladder says the question's answer type picks the tool: regions, distance, spread time or path count.
Step 1: Regions and reachability use a flood fill
A question about regions or reachability asks which cells connect, or how many separate groups exist, and a flood fill answers it. Start at any unseen land cell, visit everything reachable, then start again at the next unseen cell. The number of starts is the number of regions. This is the shape of Number of Islands, and flood fill can run on a stack or a queue.
Input: a grid and a rule for which cells count as land. Output: a count, or the size of each region. Order does not matter here, so depth-first and breadth-first both work. Both cost time proportional to the number of cells (both the breadth-first search reference and the depth-first search reference give a running time proportional to vertices plus edges, and a grid cell has at most four neighbors).
def count_regions(grid):
rows, cols = len(grid), len(grid[0])
seen, regions = set(), 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and (r, c) not in seen:
regions += 1
stack = [(r, c)]
seen.add((r, c))
while stack:
cr, cc = stack.pop()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in seen:
seen.add((nr, nc))
stack.append((nr, nc))
return regionsHere land is the number 1. On Number of Islands the cells are the strings '1' and '0', and the string '0' is truthy in Python, so compare with '1' there. You now know the first rung: count the starts. Check whether the problem allows four-way or eight-way moves before you code.
Step 2: BFS finds the shortest distance, and cells are marked when queued
Breadth-first search finds the shortest path in an unweighted grid, because it visits cells in order of distance from the start (Sedgewick and Wayne, section 4.1; see also the breadth-first search reference). A queue is a first in, first out (FIFO) list: items leave in the order they arrived. In Python, use a deque, a double-ended list with fast appends and pops at either end (collections documentation), not a list popped from the front.
Mark a cell visited when you add it to the queue, not when you remove it, because marking on removal lets two neighbors add the same cell. On the example grid in the worked example, marking on removal makes 14 queue pushes where marking on adding makes 11.1 Each duplicate is popped and thrown away, so the queue holds up to one entry per edge instead of one per cell. In a version that counts healthy cells as it pushes, a cell claimed twice is also counted twice, and the answer comes out wrong.
Input: a start cell and a target. Output: the level at which the target is first reached.
Step 3: Multi-source BFS answers how long it takes to spread
Spread-time questions, such as the time for every orange to rot, use multi-source BFS: put all sources in the queue at level zero, then count levels. The answer is the number of levels needed to reach every reachable cell, or minus one if some target cell can never be reached. That is the statement of Rotting Oranges.
Running one search per source and taking the minimum is a common misreading. It is slower and unnecessary: with every source in the queue, each cell is first reached by its nearest source, which is exactly the spread time.
Input: a grid with several sources. Output: the number of levels, or minus one. Process the queue one full level at a time, using the queue's length at the start of each level to know where the level ends. Stop when no healthy cell is left; otherwise the last level, which infects nothing, is counted by mistake. With no healthy cells at the start the answer is 0, as in the Rotting Oranges statement.
from collections import deque
def spread_time(grid): # 2 = source, 1 = healthy, 0 = empty
q, fresh = deque(), 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == 2:
q.append((r, c)) # every source starts at level 0
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while q and fresh: # stop when nothing healthy is left
for _ in range(len(q)): # exactly one level
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 1:
grid[nr][nc] = 2 # mark when queued
fresh -= 1
q.append((nr, nc))
minutes += 1
return -1 if fresh else minutesSingle-source distance from step two is the same loop with one start cell, returning the level when the target is queued. You now have the third rung.
Step 4: Counting paths is dynamic programming, not a search
Counting the paths from the top-left to the bottom-right with only right and down moves is a dynamic programming question. Dynamic programming (DP) is solving a problem from the answers to smaller copies of itself, stored in a table so each is computed once. A search that tries every route repeats the same sub-routes over and over, so its work grows far faster than the number of cells.
The rule for cell (i, j) is: paths to it equal paths to the cell above plus paths to the cell to its left, and zero if the cell is blocked. Fill the table row by row, and the last cell holds the answer.
Input: a grid with blocked cells. Output: one number. Cost: one table entry per cell. This is the last rung and the only one that is not a search. Do not use DFS or BFS here unless the question asks you to list the paths themselves.
Step-by-step description
- Count the starts of a flood fill.
- BFS from one cell, marked when queued.
- Queue every source, count levels.
- A table, not a search.
- Regions and reachability use a flood fill.
- Shortest distance in an unweighted grid uses breadth-first search from one cell.
- Spread time uses breadth-first search from every source.
- Counting paths uses dynamic programming, not search.
Regions and reachability use a flood fill. Shortest distance in an unweighted grid uses breadth-first search from one cell. Spread time uses breadth-first search from every source. Counting paths uses dynamic programming, not search.
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 the illustrative four-by-four grid below. A two is an infected cell, a one is a healthy cell and a zero is empty. Moves go four ways.
2 1 1 0
1 1 0 1
0 1 1 1
1 0 1 2The grid has 2 sources and 10 healthy cells. Multi-source BFS infects 4 cells in minute one, 4 more in minute two and 1 more in minute three. The healthy cell in the bottom-left corner is walled in by empty cells and never infected, so the answer for this grid is -1. If that cell were empty, the answer would be 3.1 The search takes 11 cells off the queue, and each is checked against four neighbors, so 44 neighbor checks in all.1
| Quantity | Value (illustrative grid) |
|---|---|
| Infected cells at the start | 2 |
| Newly infected in minute 1 | 4 |
| Newly infected in minute 2 | 4 |
| Newly infected in minute 3 | 1 |
| Healthy cells never reached | 1 |
| Answer for this grid | -1 |
| Answer if the stranded cell were empty | 3 |
| Neighbor checks | 44 |
| Queue pushes, marked when queued | 11 |
| Queue pushes, marked when removed | 14 |
| Land regions (nonzero cells, four-way) | 2, of sizes 11 and 1 |
Text description of the diagram
- Minute one infects four cells and minute two infects four more.
- One healthy cell is never reached.
Minute one infects four cells and minute two infects four more; the chart shows how few cells remain by minute three. Counting regions on the same grid with a flood fill gives 2, because the bottom-left cell is its own island. Treating the zeros as blocked cells and counting right-and-down paths from the top-left to the bottom-right with dynamic programming gives 4, against 20 on a grid with no blocked cells.1
Trade-offs and edge cases
Each tool has a place and a failure mode, and the table lists the four question types with the tool and where the answer is read from.
Text description of the diagram
- Only breadth-first search gives shortest paths in an unweighted grid.
- Path counting is dynamic programming, not search.
Only breadth-first search gives shortest paths in an unweighted grid; depth-first search can return a longer route (Sedgewick and Wayne, section 4.1; the depth-first search reference). Both searches cost time proportional to the number of cells, so the choice is about visit order and memory, not speed. Path counting is dynamic programming, not search.
Edge cases to check before coding:
- Recursion depth. A recursive DFS on a thousand-by-thousand grid can go as deep as 1,000,000 frames.1 Python caps recursion depth, and undefined changes the cap, but an explicit stack avoids the issue. See the Python interview questions for the other language traps.
- Connectivity. Four-way and eight-way moves give different answers on the same grid.
- Mutating the input. Writing a marker into the grid saves memory but destroys the input; ask first.
- Weighted moves. If cells have different costs, BFS levels no longer equal cost. That needs Dijkstra's algorithm for non-negative costs, or 0-1 BFS with a deque when every cost is 0 or 1.
- Listing paths. If you must output every path, backtracking is the tool, and the cost grows with the number of paths.
The same ideas extend beyond grids: a grid is a graph, so topological sort and cycle detection build on the same traversals with extra state, and distance questions with a ranking, such as k closest points to the origin, use other structures.
How to answer it in an interview
How do you solve grid problems like shortest path, time to spread, or counting paths?
I start by asking what the question wants. For regions or reachability, I run a flood fill from each unvisited cell and count the starts. For the shortest route, I run breadth-first search with a queue and mark each cell visited when I add it so each cell enters the queue once; breadth-first order makes the first arrival at the target the shortest distance. For time to spread, I queue every source before the first step and count levels. For the number of paths, search repeats work, so I fill a dynamic programming table with zero on blocked cells.
The spoken structure: name the answer type, name the tool, state the visit rule, then state the cost.
Common mistakes
- "DFS gives me the shortest path." (wrong) It finds a path, not the shortest. (right) "BFS visits cells by distance, so the first arrival is shortest."
- "I mark a cell visited when I take it off the queue." (wrong) Neighbors can add it several times. (right) "I mark it when I add it, so each cell enters once."
- "I run BFS from each source and take the minimum." (wrong) It repeats work. (right) "I queue every source first and run one search."
- "I count paths by searching." (wrong) The search repeats sub-routes. (right) "Paths to a cell are paths from above plus paths from the left, zero if blocked."
- "I add one for every pass of the level loop." (wrong) The final pass infects nothing, so the answer comes out one too large. (right) "I stop when no healthy cell is left, and return 0 if there were none to start."
Follow-up questions
How do you compute the time to infect all cells in a grid?
Queue every infected cell, run BFS one level at a time, and count the levels until no healthy cell can be reached. If a healthy cell is left over, return minus one. The example above takes three minutes to reach every reachable cell and then returns minus one.
How do you find disconnected components, then count grid paths with obstacles?
Run a flood fill from every unseen land cell and count the starts; that is the component count. For path counts, switch to dynamic programming: each cell adds the paths from above and from the left, and a blocked cell is zero.
Does DFS find the shortest path in a grid?
No. DFS follows one route to its end and may reach the target by a long way around. Use BFS when every move costs the same.
When should a visited mark be set in BFS?
Set it when the cell is added to the queue. Setting it on removal lets several neighbors add the same cell, which is what the 14 against 11 pushes in the example shows.
Can recursive DFS overflow on a big grid?
Yes. A thousand-by-thousand grid can need 1,000,000 nested calls, far past Python's default limit. Use an explicit stack, or raise the limit with sys.setrecursionlimit knowing the risk.
How do you count unique islands, meaning distinct shapes?
Flood fill each island, record every cell as an offset from the island's first cell in scan order, and store the sorted offsets in a set. The size of the set is the number of distinct shapes, the "unique lands" wording candidates report.
- Sort a grid question by its answer type before choosing a tool.
- Regions use a flood fill; distance uses BFS; spread time uses multi-source BFS; path counts use dynamic programming.
- Mark cells visited when queued, not when removed.
- DFS does not give shortest paths; BFS and DFS cost the same time order.
- Check four-way versus eight-way moves, and recursion depth, before coding.
Sources
- Algorithms, 4th edition, section 4.1 Undirected Graphs (breadth-first search) — Sedgewick and Wayne, Algorithms, 4th ed. (2011), Princeton companion site, 1 Jan 2011
- Breadth-first search — Wikipedia (reference page, accessed 2026-10-26), 26 Oct 2026
- Depth-first search — Wikipedia (reference page, accessed 2026-10-26), 26 Oct 2026
- Flood fill — Wikipedia (reference page, accessed 2026-10-26), 26 Oct 2026
- collections: container datatypes (deque) — Python Software Foundation documentation, 26 Oct 2026
- sys: system-specific parameters (setrecursionlimit) — Python Software Foundation documentation, 26 Oct 2026
- Rotting Oranges (problem 994) — LeetCode (problem statement), 26 Oct 2026
- Number of Islands (problem 200) — LeetCode (problem statement), 26 Oct 2026
