Clone Graph
Map original nodes to their clones as you traverse.
Approach
DFS or BFS from the start node, keeping a hash map from each original node to its copy. When you first see a node, create its clone; then wire each clone's neighbors by looking them up (creating them on demand). The map both memoizes and prevents infinite loops on cycles.
Time complexity
O(V + E)
Space complexity
O(V)
Common mistake
Creating duplicate clones for the same node because you didn't check/populate the map before recursing.
See it run, step by step
Generate an interactive lesson for Clone Graph — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Clone Graph