Pattern Recognition Drill
Medium Advanced Graphs
The Problem
Deep copy a graph. Each node has a value and neighbor list.
What approach would you use?
Think about it before scrolling down.
DFS with hashmap {original: clone}. For each neighbor: if cloned, reuse; else clone and recurse. O(V+E).
BFS with same hashmap approach. O(V+E).
Common Trap
Must handle cycles — the hashmap prevents infinite loops by checking if a node is already cloned.