Synthesis: which pattern to use?
Five matrix patterns covered. Time to train the reflex: read a grid problem and know which tool to pull out — with justification.
The section's decision tree
1. Do I need to TRAVERSE/PRODUCE the matrix in a special order (spiral, layers)?
→ LAYER-BY-LAYER TRAVERSAL (four shrinking bounds)
2. Do I need to TRANSFORM the matrix without extra memory (rotate, zero)?
→ IN-PLACE: decompose (transpose + reverse) and/or use the 1st row/column
as markers
3. Is the question about CONNECTED REGIONS (islands, areas, filling)?
→ DFS / FLOOD FILL (permanent mark; covers the region)
4. Do I need to find/count specific PATHS (a word, all paths)?
→ BACKTRACKING (DFS with a temporary mark: mark → explore → unmark)
5. Is the question "the SHORTEST path / fewest steps"?
→ BFS (queue, layers of increasing distance)
And the reflexes for the whole section: name both dimensions in the Big-O (O(m·n), not O(n²)), always check the bounds before accessing a neighbor, and remember that a grid is a graph — DFS/BFS are the core tools.
The complete map of the section
| Pattern | Key question | Structure | Time | Space |
|---|---|---|---|---|
| Spiral traversal | "traverse in a spiral/layers" | 4 bounds | O(m·n) | O(1) |
| In-place transformation | "rotate/zero without a copy" | indices + markers | O(m·n) | O(1) |
| DFS / flood fill | "connected regions" | stack (recursion) | O(m·n) | O(m·n) |
| Backtracking | "specific path / all" | DFS + undo | O(m·n·4ᴸ) | O(L) |
| BFS | "shortest path" | queue | O(m·n) | O(m·n) |
The idea that ties half the section together: the grid is a graph, and DFS (deep), backtracking (deep + undo) and BFS (wide) are three ways to traverse it, each for a kind of question. You leave here ready for the Graphs section, where these same algorithms appear without the "crutch" of the regular grid.
Section quiz
Statements you have not seen in the lessons. Identify the pattern and the why. 7+ correct: ready for the exam.
🧠 Section quiz: Matrix
0/81. 'Compute the area of the largest island of 1s in a grid.' Which pattern?
2. 'How many steps for a rotten orange to rot all its neighbors, in minutes?' (multi-source). Which pattern?
3. 'Generate an n×n matrix filled in a spiral with 1..n².' Which pattern?
4. 'Find whether there is a path that spells a word through adjacent cells (without reusing).' Which pattern?
5. 'Distance of each cell to the nearest 0 (01 Matrix).' Which pattern?
6. Why is the complexity of visiting a 1000×3 matrix O(m·n) = 3000, and not O(n²) = 1,000,000?
7. What is the master idea connecting DFS, backtracking and BFS in this section?
8. 'Capture the regions of O surrounded by X (those that do not touch the edge).' What is the insight?
Ready for the exam?
The Matrix section's final exam has three new problems — easy, medium and hard — with hidden cases. The hard one (capturing surrounded regions) calls for the insight of inverting the problem and running DFS from the edges: exactly the kind of reasoning the decision tree above trains.
Good luck on the exam! Go back to the section page and click "Final exam".