Clone Graph
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Make a deep copy of a connected undirected graph given one node. Each node has a value and a list of neighbours.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What goes wrong if you recursively copy neighbours without remembering anything?
- Hint 2A dictionary original -> copy doubles as the visited set.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Photocopying a friend circle. For every person you create an identical twin with the same name. Whenever you meet a friend of the person you are copying, you check your register of "original -> twin": if the friend already has a twin you use it, otherwise you create it and note it in the register. Then you connect the twin of the person to the twin of the friend.
- The obvious way
Without a map you would copy forever in a cycle; the map is the solution.
- The key insight
Create the copy of the start node and a queue holding the start. Pop a node; for every neighbour, if it has no copy yet create one and queue it; then add the neighbour's copy to the node's copy's neighbour list. Each node and edge is handled once.
- The algorithm
- No start: return nothing.
- copies = {start: new twin}; queue = [start].
- For each neighbour without a twin: create it and queue it.
- Link the twin to the neighbour's twin. Return the start's twin.
Watch it run
Examplesquare graph 1-2, 2-3, 3-4, 4-1
Make twin 1'. Register: 1 -> 1'. Queue: [1].
register: 1
Where people slip
- Register the copy before you go to the neighbours, or cycles recurse forever.
- Return the copy of the START node, not the start node itself.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import deque
def clone_graph(node):
if node is None:
return None
twin_of = {node: Node(node.val)} # register: original -> twin
waiting = deque([node])
while waiting:
person = waiting.popleft()
for friend in person.neighbors:
if friend not in twin_of:
twin_of[friend] = Node(friend.val) # first time we meet this friend
waiting.append(friend)
twin_of[person].neighbors.append(twin_of[friend])
return twin_of[node]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.