LeetCode · DFS
DFS Problem Set
Depth-first search is the natural tool for connected components, cycle detection, post-order dependency reasoning, and backtracking-style path exploration. If the prompt asks you to explore one branch fully before trying another, DFS should be one of your first candidates.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | components | LC 200 · Number of Islands | Launch DFS from each unvisited land cell. Each launch floods exactly one connected component, so the number of launches is the answer. |
| Medium | cycle-detect | LC 207 · Course Schedule | Use three-color DFS on the directed graph. Revisiting a gray node means a back edge and therefore a cycle. |
| Medium | topological | LC 210 · Course Schedule II | DFS post-order naturally builds a topological order: push a node after exploring all of its outgoing edges, then reverse. |
| Medium | graph-copy | LC 133 · Clone Graph | Memoize original → clone nodes during DFS so cycles and shared neighbors are reconstructed exactly once. |
| Medium | grid-reachability | LC 417 · Pacific Atlantic Water Flow | Reverse the thinking: DFS outward from the ocean borders. Cells reachable from both DFS passes can flow to both oceans. |
| Medium | path-enumeration | LC 797 · All Paths From Source to Target | Track one shared path list, recurse into neighbors, and backtrack with pop. Because the graph is a DAG, no visited set is needed. |
Practice note: All listed DFS problems on this page now have dedicated solution write-ups, so you can go straight from the concept page into a worked example for each major DFS pattern.