Clone Graph – Solution & Complexity
Watch: Clone Graph with DFS and an old → new hash map
Naive recursion clones a node and then every neighbor, which loops forever on a cycle and would make duplicate copies anyway. Keep a hash map from each original node to its copy and store the copy before visiting its neighbors: when a cycle leads back, return the existing copy. The trace on the 4-node square creates 4 copies, each exactly once, and 8 neighbor links. Handle None and a single node with no neighbors. O(V + E) time, O(V) space.
Solution Walkthrough
Step 1: Recognize the Pattern
The key pattern is: DFS copies each vertex and adjacency row once. Identify the state and invariant before coding.
Step 2: Build the Algorithm
Advance one state transition at a time. Mark or update state before exploring dependent work.
Step 3: Check Edge Cases
Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.
Step 4: Solution and Complexity
Time: O(V + E). Space: O(V + E).