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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes