~20 minutes · Day 53 · graph cloning · Python
Tonight's problem is Clone Graph. Interviewers like it because the code is short, but the mistake is deep: if you copy a graph the way you copy a tree, a cycle can send your recursion around forever. The win is to remember every original node the first time you clone it.
A hashmap from original node to its clone doubles as the visited set — create the clone on first visit, reuse it ever after.
That's the whole pattern. The LeetCode statement gives you a node with a value and a list of neighbors. Your output must be a new graph with the same shape, not references back into the old graph. In Python, the hashmap is a dict; average membership and lookup are O(1) (Python wiki: time complexity).
The map keeps object identity: a back-edge finds the existing clone instead of creating a duplicate.
The tempting recursive copy is to create a node, then recursively copy every neighbor:
def cloneGraph(node):
clone = Node(node.val)
for nei in node.neighbors:
clone.neighbors.append(cloneGraph(nei))
return clone
This is not a valid graph algorithm. If node 1 points to node 2 and node 2 points back to node 1, this code keeps cloning the same cycle. The missing question is: have I already created the clone for this original node?
def cloneGraph(node):
old_to_new = {} # original node -> cloned node
def dfs(cur):
if cur in old_to_new:
return old_to_new[cur] # reuse clone; stop cycles
clone = Node(cur.val) # first visit creates it
old_to_new[cur] = clone # mark before neighbors
for nei in cur.neighbors:
clone.neighbors.append(dfs(nei))
return clone
return dfs(node) if node else None
The important order is create, store, then explore neighbors. Storing the clone before the neighbor loop means a back-edge can find the unfinished clone instead of starting a second copy.
Imagine a node has two pointers: next and random. You need to deep-copy the whole pointer structure. Before opening the reveal, predict the map: what should the key be, and what should the value be?
def copy_pointer_structure(node):
old_to_new = {}
def dfs(cur):
if not cur: return None
if cur in old_to_new: return old_to_new[cur]
clone = RNode(cur.val)
old_to_new[cur] = clone
clone.next = dfs(cur.next)
clone.random = dfs(cur.random)
return clone
return dfs(node)Same invariant. The key is the original object; the value is its clone. The edges changed names, but the map still prevents duplicate clones and stops cycles.
| Approach | Time | Space |
|---|---|---|
| Naive recursion, no map | Not bounded on cycles | Grows until failure |
| Hashmap from old node to clone | O(V + E) | O(V) |
The good version visits each original node once and copies each neighbor edge once. The extra space is the price of identity memory: one clone entry per original node.
1. What should the clone map store?
2. Spot the bug in this order:
clone = Node(cur.val)
for nei in cur.neighbors:
clone.neighbors.append(dfs(nei))
old_to_new[cur] = clone3. Which prompt should trigger this pattern?
4. When should a node clone be created?
Solve Clone Graph on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode.
old_to_new, storing the clone before the neighbor loop.Watch NeetCode — Clone Graph after your attempt, as the compare step. Listen for the moment where the map becomes both the clone lookup and the visited set.