Depth-First Search, Connected Components, And Cycles
Asked of: Software Engineer
Last updated

What's being tested
Depth-first search questions test whether you can traverse implicit or explicit graphs, mark visited state, and aggregate connected components without double-counting. Expect grids, adjacency lists, island sizing, cycle detection, and recursive-vs-iterative tradeoffs with clear O(V + E) or O(mn) complexity.
Patterns & templates
-
Grid DFS — use
dfs(r, c)with 4-neighbor deltas; bounds-check before visiting;O(mn)time,O(mn)worst-case stack. -
Connected components — loop over every node/cell, start
dfsonly if unvisited, increment component count or accumulate size. -
Visited marking — use
set(), boolean matrix, or in-place mutation like changing'1'to'0'; avoid revisiting cyclic paths. -
Iterative DFS — replace recursion with explicit
stack; safer for large grids or deep graphs where recursion may overflow. -
Cycle detection — for undirected graphs, track
parent; for directed graphs, use color states:WHITE,GRAY,BLACK. -
Adjacency construction — convert edge lists into
defaultdict(list)before traversal; include isolated nodes if the problem counts them. -
Complexity narration — say
O(V + E)for graphs,O(mn)for grids; space is visited plus recursion/stack depth.
Common pitfalls
Pitfall: Marking a cell visited after recursive calls can cause infinite recursion or double-counting; mark before exploring neighbors.
Pitfall: Treating diagonal cells as connected when the prompt specifies 4-directional connectivity.
Pitfall: Using recursive DFS blindly on large inputs; mention iterative DFS when depth could approach
Vormn.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Find the Extra EdgeApple · Software Engineer · Technical Screen · hard
- Solve mixed coding tasks from interviewsApple · Software Engineer · Technical Screen · medium
- Solve 15 common Apple coding questionsApple · Software Engineer · Technical Screen · medium
- Solve 15 common interview problemsApple · Software Engineer · Technical Screen · medium
- Solve interval, grid-fill, and heap tasksApple · Software Engineer · Technical Screen · medium
- Implement DFS for connected componentsApple · Software Engineer · Onsite · Medium
- Compute island size in gridApple · Software Engineer · Technical Screen · Medium
Related concepts
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms
- Graphs, Grids, And Connected ComponentsCoding & Algorithms
- Graph Traversal And Shortest PathsCoding & Algorithms