Micro-questions over the matrix traversal pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The reframing
1. What is a grid, as a graph?
Answer
Each cell is a node, and each cell is connected to its neighbours — usually 4, sometimes 8.
2. What follows from that?
Answer
DFS and BFS apply directly. There is no new algorithm here, just a different way of expressing “neighbours”.
3. What is an implicit graph?
Answer
One where nodes and edges are defined by the structure rather than explicitly stored — neighbours are computed, not looked up.
4. How are neighbours computed?
Answer
From (row, col) using direction offsets: [(0,1), (0,-1), (1,0), (-1,0)].
B. What the pattern adds
5. What is the one thing this pattern adds on top of plain graph traversal?
Answer
The bounds check — 0 <= r < rows and 0 <= c < cols.
6. Why is it needed here and not in a normal graph?
Answer
There is no explicit neighbour list to bound the search, so the traversal has to check for the grid’s edges itself.
7. What does marking a cell visited do here?
Answer
The same thing it does in any graph traversal — avoids revisiting and infinite loops.
C. Flood fill
8. Describe it.
Answer
From a start cell, recursively visit all neighbours holding the old colour, overwriting each with the new one.
9. Why the early if old_color == new_color: return?
Answer
Otherwise overwriting does not change anything, so nothing is ever “marked visited” and the recursion never terminates.
10. What is the real-world name for flood fill?
Answer
The bucket fill tool in paint programs.
D. Counting regions
11. How does Number of Islands differ from flood fill?
Answer
Instead of one fill from a given start, loop over every cell and start a new DFS/BFS from any unvisited land cell.
12. Why does that count correctly?
Answer
Each traversal you start from is a new island, and it marks everything connected as visited so it is not counted twice.
13. How would you do it with BFS instead?
Answer
Identical structure — replace the recursive call with a queue, enqueueing each unvisited land neighbour and marking it visited on enqueue.
E. Trade-offs
14. What breaks on very large grids?
Answer
Recursion depth. Use an iterative BFS/DFS with an explicit stack or queue.
15. What changes for 8-directional problems?
Answer
Extend the directions list with the four diagonals. Everything else is unchanged.
16. When can you not mark visited by overwriting?
Answer
When the grid values must be preserved — then you need a separate visited set.
17. Summarise the pattern in one sentence.
Answer
A grid is a graph whose edges you compute instead of store — so the only new code is the bounds check.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Matrix Traversal — the pattern
- DFS Pattern — Question Bank
- BFS Pattern — Question Bank
- Graph Representations — Question Bank — where implicit graphs are defined
Software engineering
Infrastructure & security
Computer science
Hardware & engineering