DSA & Algorithms
Part 8 of 16 · DSA Advanced & Company FavoritesMatrix Traversal - Spiral, Islands, DFS/BFS on grids
Spiral order, rotate, islands variants, and grid BFS/DFS depth beyond basic flood fill.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The input is a grid
Prefer
Walk neighbors or peel the border
DFS floods. BFS measures unweighted steps. Spiral peels layers.
- Mark visited before enqueueing.
- 4-direction unless the prompt says diagonal.
- The spiral stops when the layer crosses.
Alternative
Copy the grid into a list of cells and sort
Sorting does not preserve adjacency or layer order.
- You revisit a land cell.
- You BFS when any path would do and blow the queue.
- You rotate by writing a formula you cannot dry-run.
Pick flood, distance, or peel
The grid is the graph.
- 1
Choose 4 or 8
Diagonal only when the prompt says so. - 2
DFS or BFS
Flood versus unweighted distance. - 3
Or peel layers
Spiral walks the current border, then shrinks.
Overview
Spiral order, rotate, islands variants, and grid BFS/DFS depth beyond basic flood fill.
When companies ask this
Recognition cues: spiral / rotate matrix; number of islands / max area; surrounded regions; shortest path in grid; pacific atlantic.
Deepens wave-1 dsa-graphs-dfs-bfs with matrix-specific patterns.
Mental model
Decisions
- 1
1. The grid is a graph
- next2. Need distance?
- ?
2. Need distance?
- yes3. BFS by layers
- no4. DFS flood or peel a spiral
- 3
3. BFS by layers
- 4
4. DFS flood or peel a spiral
Lesson map
Matrix Traversal - Spiral, Islands, DFS/BFS on grids
Spiral order, rotate, islands variants, and grid BFS/DFS depth beyond basic flood fill.
Architecture. 1. The grid is a graph Ready. 2. Need distance? Ready. 3. BFS by layers Ready. 4. DFS flood or peel a spiral Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Grid["1. The grid is a graph Ready"] Dir["2. Need distance? Ready"] BFS["3. BFS by layers Ready"] DFS["4. DFS flood or peel a spiral Ready"] Grid -->|continues| Dir Dir -->|yes| BFS Dir -->|no| DFS
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- Spiral O(RC); islands O(RC); multi-source BFS O(RC).
- Pitfalls: spiral double-count corners; mutating input; 8-dir vs 4-dir.
Interviewer traps
LeetCode drill (real problems)
- Spiral Matrix
- Rotate Image
- Number of Islands
- Max Area of Island
- Surrounded Regions
- Pacific Atlantic Water Flow
- 01 Matrix
- Shortest Path in Binary Matrix
- Set Matrix Zeroes
YouTube
Interview Q&A
Spiral layers?
Answer
Shrink r1,r2,c1,c2; guard single row/col.
Islands count?
Answer
DFS/BFS flood each unvisited land.
Multi-source BFS?
Answer
Seed queue with all sources (zeros / gates).
Rotate 90?
Answer
Transpose then reverse each row.
Surrounded regions?
Answer
DFS from border 'O'; flip rest.
Related wave-1?
Answer
graphs-dfs-bfs, dp-2d, backtracking.
Diagonal BFS?
Answer
8 directions for binary matrix shortest.
Set zeroes O(1) space?
Answer
Use first row/col as markers.