Stage 1 · Code
Graphs & Backtracking
Graph Drills
Connected components, cycle detection, matrix traversal, and backtracking — train the patterns that separate graph-solvers from the rest.
12 min readLeetCode Patterns for InterviewsCode
How to Drill Graphs
Graph problems are really four decisions: adjacency representation (list vs matrix), traversal choice (DFS vs BFS), visited tracking (set vs in-place mutation), and state accumulation (count, path, distance). Do those four quickly and the algorithm writes itself.
DFS for reachability, BFS for shortest paths
When the question asks 'can you reach?' or 'how many components?', DFS is simpler. When it asks 'shortest path' or 'minimum steps', BFS guarantees optimality on unweighted graphs.
Adjacency list vs adjacency matrix
Graph Patterns
| Pattern | Algorithm | Tells |
|---|---|---|
| Connected Components | DFS/BFS on every unvisited node | Number of islands, friend circles |
| Cycle Detection | DFS with visiting/safe states OR union-find | Course schedule dependency graph |
| Matrix Traversal | 4-directional DFS/BFS with bounds check | Pacific Atlantic water flow, rotten oranges |
| Topological Sort | Kahn's algorithm (in-degree queue) | Build order, task scheduling |
| Shortest Path (unweighted) | BFS level-order | Word ladder, nearest exit |
| Backtracking Search | DFS + prune on constraint violation | N-Queens, word search |
Problems
#200Number of IslandsMediumConnected components / Matrix DFS · O(m × n) time · O(m × n) worst case space#133Clone GraphMediumDFS with hash map memo · O(V + E) time · O(V) space#207Course ScheduleMediumCycle detection / Topological sort · O(V + E) time · O(V + E) space#417Pacific Atlantic Water FlowMediumMatrix traversal from borders · O(m × n) time · O(m × n) space#79Word SearchMediumBacktracking on grid · O(m × n × 4^L) where L = word length time · O(L) recursion space
Key Points
- Visited is everything — forgot visited = infinite loop. Use in-place mutation for grids, hash map for cloned nodes.
- BFS for minimum moves — unweighted shortest paths need a queue, not recursion.
- Cycle detection in directed graphs — use three-colour DFS (white/gray/black) or Kahn's in-degree.
- Matrix = implicit graph — neighbours are 4 (or 8) directional offsets, bounds-check first.
- Backtracking needs pruning — fail fast when constraints violate, restore state after exploring.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.