Learning Outcome
After this lesson, you should be able to use a map from original nodes to clone nodes so cycles do not create duplicate copies.
Problem Statement
Given a reference to a node in a connected undirected graph, return a deep copy of the graph.
| Input | Output | Why |
|---|---|---|
adjList = [[2,4],[1,3],[2,4],[1,3]] | A separate graph with the same values and neighbor links | Each original node has exactly one clone, and cloned neighbors point to cloned nodes. |
Brute Force Approach
Create a new node every time a neighbor is seen. In cyclic graphs this duplicates nodes and can recurse forever.
Optimized Approach
DFS from the start node. Store each original node in a map as soon as its clone is created, then recursively clone neighbors.
Exact Pseudocode
clone(node):
if node is null:
return null
if node exists in map:
return map[node]
copy = new Node(node.val)
map[node] = copy
for neighbor in node.neighbors:
copy.neighbors.add(clone(neighbor))
return copyReference Code
class Solution:
def cloneGraph(self, node):
clones = {}
def dfs(cur):
if not cur:
return None
if cur in clones:
return clones[cur]
copy = Node(cur.val)
clones[cur] = copy
for nei in cur.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node)Sample Dry Run
| Step | State | Result |
|---|---|---|
| Visit node 1 | Create clone 1 and store map[1] | Cycle protection starts |
| Clone neighbor 2 | Create clone 2 | Add it to clone 1 neighbors |
| Neighbor points back | DFS sees node 1 already in map | Reuse clone 1 |
| Finish | Every original maps to one clone | Return clone of start |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(v + e) | Every node and neighbor edge is visited once. |
| Space | O(v) | The clone map and recursion stack store graph nodes. |
Edge Cases
- Null input should return null.
- Cycles must reuse existing clones.
- Do not share original neighbor references in the clone.
Interview Checklist
- Put the clone in the map before cloning neighbors.
- Use node references as map keys.
- Return the cloned start node, not the original node.
FAQs
Why store clone before neighbors?
A cycle can point back to the current node. The map must already know the clone to stop infinite recursion.
Is this a deep copy?
Yes, every node is new, and every neighbor link points to cloned nodes.
What is the core pattern?
DFS with an original-to-copy hash map.