LeetEye LeetEye
Medium Graph Traversal ~5 min

Clone Graph

graphs clone-graph

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

Examples

Example 1
Input: nums = [1,2,3]
Output: result
Key Insight

Map old nodes to new nodes. When setting neighbors, look up the clone.

DFS/BFS with old→new hashmap. For each node: create clone if not in map, then set neighbors to cloned versions (lookup in map).

How to Approach This Problem

Pattern Recognition: When you see keywords like clone graph graphs, think Graph Traversal.

Step-by-Step Reasoning

1 Copying node.neighbors directly fails because:
Answer: It still points to original nodes
We need neighbors to point to NEW cloned nodes, not originals.
2 The old→new hashmap:
Answer: Maps original nodes to their clones
When we need the clone of a node, we look it up in the map.
3 For cycles (node A's neighbor is B, B's neighbor is A):
Answer: B and C
If we've already cloned a node (it's in hashmap), reuse that clone instead of creating another.
4 We can traverse the graph using:
Answer: Either
Both work. We just need to visit all nodes.
5 We create a clone:
Answer: When we first visit a node
Create clone immediately, add to hashmap, then process neighbors.
6 For clone of node N, its neighbors are:
Answer: Clones of each neighbor (from hashmap)
Each neighbor must be the cloned version, which we look up (or create).

Solution

def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None
    
    old_to_new = {}
    
    def dfs(node):
        if node in old_to_new:
            return old_to_new[node]
        
        # Create clone
        copy = Node(node.val)
        old_to_new[node] = copy
        
        # Clone neighbors
        for neighbor in node.neighbors:
            copy.neighbors.append(dfs(neighbor))
        
        return copy
    
    return dfs(node)

Complexity Analysis

Time O(V + E)
Space O(V)

Master This Pattern

Build intuition with interactive MCQs. Practice Graph Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye