← Back to problems Solve on LeetCode → See #323 Components →

Clone Graph

LeetCode 133 • Medium • Graphs

Input: adj list [[2,4],[1,3],[2,4],[1,3]] (nodes 1–4) → deep copy with same structure.
BFS/DFS: map old→new, clone on first visit, wire neighbors from the map.

TimeO(V+E)visit each node & edge

SpaceO(V)map + queue

Queue: []Cloned: []

Current (original)

In queue

Cloned copy

Processed

Queue

empty

Map

{}

Speed:

Ready

Press Play. BFS from node 1: clone into old_to_new, enqueue unseen neighbors.

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. Hash map old→new prevents infinite loops on cycles.

═══ CLONE GRAPH — BFS + MAP ═══

PATTERN ▸ BFS/DFS + old_to_new map O(V+E)

① SEED

old_to_new[node] = Node(node.val); queue = [node]

② BFS LOOP

cur = queue.popleft()

for nb: clone if missing; link old_to_new[cur].neighbors

③ RETURN

return old_to_new[node]

▼ your implementation ▼

Verify your solution: