FAANGPrep Sprint
Clone Graph
Deep copy a connected undirected graph.
Examples
Return a deep copy of the graph.
Problem Understanding
You are handed one node of a connected, undirected graph.
Build and return a deep copy of the whole graph.
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
LEFT = ORIGINAL · RIGHT = COPY (1′ COPIES 1) · ARROW = LINKED FROM ONE END SO FAR
CALL clone(1)
Copies
0
Map hits
0
call stack
No clone() running
copies map
Empty
Call clone on node 1, the node LeetCode hands in
Next
clone(1): no copy yet — create a new node with value 1
adjList
The original graph is on the left and the copy grows on the right. A copy appears the moment clone creates it and goes into the map straight away. A copy edge is first an arrow — one node’s neighbour list updated — and becomes a plain line when the other end links back. Each call that finds its node already in the map is a map hit: the recursion stops there instead of going round the cycle again.