Depth-First Search
Medium
Clone Graph
Deep copy a connected undirected graph.
10 min read
Solve on LeetCodeExamples
Input:adjList = [[2,4],[1,3],[2,4],[1,3]]
Output:[[2,4],[1,3],[2,4],[1,3]]
Explain:
Return a deep copy of the graph.
Problem Understanding
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone).
Deep Copy: New nodes, new edges. You cannot return references to the original nodes.
Algorithm Strategy
We need to traverse the entire graph and create a copy of each node exactly once.
Key Tool: HashMap<OldNode, NewNode>.
- Check Map: If we already cloned this node, return the
NewNodefrom the map (handles cycles). - Create: If not, create
NewNode(val)and add to map. - Recurse: Iterate through
OldNode.neighbors. For each neighbor, recursively callclone(neighbor)and add the result toNewNode.neighbors.
Visualization
Step 1 / 18
Adjacency List(Map<Node, List>)
Start Clone Graph. We need to create a deep copy of each node.
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.