The problem
Given one node of a connected undirected graph, return a deep copy of the whole graph: new nodes with the same values and the same connections.
Input: 4 junctions: 1–2, 2–3, 3–4, 4–1 Output: an identical new graph
Picture it
Picture photocopying a city map, one junction at a time. We walk the map with a queue and keep a table “original junction → its copy”. When we meet a neighbour we haven’t copied yet, we copy it and add it to the queue; either way we connect the copies.
How to recognise it
- You must build a copy of a linked structure whose nodes point to each other, not just read it.
- The structure is a graph: nodes can be reached by more than one path, and cycles are possible (an undirected edge is already a two-node cycle).
- Copies must keep the same connections: if two nodes shared a neighbour, their copies must share the copy of that neighbour.
- You are handed one node, and the problem says the graph is connected, so one traversal reaches everything.
Start with brute force
The obvious plan is a recursive copy: make a new node, then copy each neighbour and attach it. On a graph with a cycle this never stops, because node A copies B, B copies A, and so on. A safe brute force first collects all nodes in a list, then builds the copies and wires them up by looking each neighbour up in the list.
def clone_brute(node):
if not node:
return None
olds, i = [node], 0
while i < len(olds):
for nb in olds[i].neighbors:
if nb not in olds: # list scan: O(V)
olds.append(nb)
i += 1
news = [Node(o.val) for o in olds]
for o, n in zip(olds, news):
for nb in o.neighbors:
n.neighbors.append(news[olds.index(nb)]) # O(V) again
return news[0]
Every edge costs a list scan of up to V entries, so time is O(V·E), which is O(V²) up to a quadratic number of edges. The list stores every node once, so space is O(V). LeetCode caps the graph at 100 nodes, so this would pass there, but with 10^5 nodes it would take around 10^10 steps or more.
From brute force to the idea
- Find the waste.
nb not in oldsandolds.index(nb)both search a list to answer "have I met this node before, and where is its copy?" - One map answers both questions. A dictionary from each original node to its copy tells you whether a node was already copied (it is a key) and gives you the copy directly (the value). Nodes are hashed by identity, so two different nodes with the same value stay separate.
- Create on first sight. Start a queue with the given node. When you pop
curand meet a neighbournbnot yet incopies, create its copy and queue it. - Wire every edge. Whether the neighbour is new or old, append its copy to
copies[cur].neighbors. Because this line runs for every neighbour of every node, edges back to old nodes are kept.
The key idea: an old-to-new dictionary is both the visited set and the way to find the copy.
The key idea
BFS/DFS with an old→new dictionary so each node is copied once and cycles don’t loop forever. O(V + E).
Python solution
def clone_graph(node):
if not node:
return None
copies = {node: Node(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nb in cur.neighbors:
if nb not in copies:
copies[nb] = Node(nb.val)
q.append(nb)
copies[cur].neighbors.append(copies[nb])
return copies[node]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(V·E): a list scan for each edge | O(V): the lists of old and new nodes |
| Dictionary BFS (shown code) | O(V + E): each node is created and queued once, each edge is handled once | O(V): the dictionary and queue (the copy itself is also O(V + E)) |
Edge cases
None(empty graph): returnsNone.- One node with no neighbours: returns a new node with an empty list.
- Self-loop (a node lists itself): the copy lists itself, not the original.
- Parallel entries (a node lists the same neighbour twice): both entries are copied, and both point to the same copy.
- Cycles: handled, because a node already in
copiesis never queued again. - Missing class: the shown code assumes
Node(val)with aneighborslist andfrom collections import deque. It uses a queue, so a long chain of nodes causes no recursion error.
Common mistakes
- Appending the neighbour's copy only inside the
if nb not in copiesblock, which loses every edge that leads back to an already-copied node. - Copying neighbours recursively without a map, which loops forever on cycles.
- Storing copies by value (
val -> copy) when values might repeat; the problem has unique values, but identity is the safer key. - Returning a node of the original graph by mistake, so the "copy" shares nodes with the input.
Each node now has edges, a list of (neighbour, weight) pairs instead of neighbors. Clone the graph so the copy keeps every weight. Describe what changes, then write it if you like.
Compare with our answer
The traversal and the dictionary stay the same. Only the pair unpacking changes, and the weight is copied as is, because a number needs no cloning.
def clone_weighted(node):
if not node:
return None
copies = {node: WNode(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nb, w in cur.edges:
if nb not in copies:
copies[nb] = WNode(nb.val)
q.append(nb)
copies[cur].edges.append((copies[nb], w))
return copies[node]
Time O(V + E), space O(V) for the map and queue.
A strong answer mentions: reusing the old-to-new dictionary, copying the weight alongside the copied neighbour, and appending the edge for every neighbour, not only new ones.
1. A linked list has a next pointer and a random pointer that may point to any node in the list, or to None. You must build a deep copy. Which approach fits best?
Random pointers make the structure a general graph, so you need a way to find the copy of any original node. An old-to-new dictionary does that. Plain recursion can loop or duplicate nodes.
2. Why does Clone Graph need the dictionary even though a BFS already has a queue?
The queue only decides the visiting order. The dictionary serves as the visited set and the lookup from original to copy, which is needed when a cycle or a second path reaches a node again.
3. A learner moves copies[cur].neighbors.append(copies[nb]) inside the if nb not in copies: block. Which input is now copied wrongly?
In the first three inputs every node is met for the first time through one edge, so the line still runs for each edge. In the undirected edge, node 2 looks back at node 1, which is already in copies, so that edge is dropped and the copy of node 2 has no neighbours.
Score 60% or more and the lesson is marked complete.