4.20.2 — Clone Graph

LeetCode 133 · Medium · ★ Blind 75

The problem

Return a deep copy of a connected undirected graph. Each node has a value and a list of neighbours.

1 --- 2
|     |
4 --- 3      →  an identical graph made of entirely new nodes

The pattern

Two problems at once.

The graph has cycles, so a naive recursive copy would loop forever: copying node 1 needs node 2, which needs node 1 again.

Nodes are shared. Node 3 is a neighbour of both 2 and 4, and it must be copied once, with both copies pointing at the same new node. Copy it twice and the shape is wrong.

Both are solved by the same thing: a map from each original node to its copy.

Before copying a node, check the map. If it is there, you have already made it — return the existing copy. That is what stops the infinite loop and what keeps shared nodes shared.

This is 4.9.5 Copy List with Random Pointer on a graph. Same map, same reason, different traversal. Seeing them as one problem is the point.

The solution

Python

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

        old_to_new = {}

        def dfs(cur):
            if cur in old_to_new:
                return old_to_new[cur]        # already copied — stops the cycle

            copy = Node(cur.val)
            old_to_new[cur] = copy            # register BEFORE recursing

            for nei in cur.neighbors:
                copy.neighbors.append(dfs(nei))

            return copy

        return dfs(node)

TypeScript

function cloneGraph(node: GNode | null): GNode | null {
  if (!node) return null;
  const map = new Map<GNode, GNode>();

  function dfs(cur: GNode): GNode {
    const existing = map.get(cur);
    if (existing) return existing;

    const copy = new GNode(cur.val);
    map.set(cur, copy);

    for (const nei of cur.neighbors) {
      copy.neighbors.push(dfs(nei));
    }
    return copy;
  }

  return dfs(node);
}

Register the copy in the map before recursing into the neighbours. This is the line that matters.

If you registered it afterwards, then copying node 1 would recurse into node 2, which would recurse back into node 1 — still absent from the map — and the recursion would never end. Registering first means the cycle comes back, finds the entry, and returns immediately.

The copy is created empty and filled in during the recursion. At the moment it goes into the map it has no neighbours yet, and that is fine — by the time the outermost call returns, every neighbour list has been filled.

Objects as keys, compared by identity. Exactly right here: two different nodes with the same value must stay different. Note this is the opposite of 4.4.4 Group Anagrams, where identity comparison was the bug. Ask which one you want: identity when tracking specific objects, value when grouping equal ones.

The BFS version

from collections import deque

def cloneGraph(self, node):
    if not node: return None
    old_to_new = {node: Node(node.val)}
    queue = deque([node])

    while queue:
        cur = queue.popleft()
        for nei in cur.neighbors:
            if nei not in old_to_new:
                old_to_new[nei] = Node(nei.val)     # create on first sight
                queue.append(nei)
            old_to_new[cur].neighbors.append(old_to_new[nei])

    return old_to_new[node]

Same logic, no recursion, so no stack depth limit. Note the neighbour link is added outside the if — the copy must be linked every time the edge is seen, even though the node is only created once.

Use BFS when the graph could be large enough to overflow the stack.

Complexity

O(V + E) time — each node is created once and each edge is walked once. In an undirected graph each edge is walked twice, once from each end, which is still O(E).

O(V) space for the map, plus O(V) for the recursion or queue.

Where this goes next

• Copy List with Random Pointer — the same map on a linked list. 4.9.5.
• Deep copy in real code — structuredClone, Python's deepcopy, and any serialiser that supports shared references all keep an identity map for exactly this reason. Without it, a cyclic object graph crashes the copier, which is why JSON.stringify throws on a cycle.
• Clone a binary tree with random pointers — same idea again.

The rule: to copy any structure with cycles or shared nodes, keep a map from original to copy and register each copy before following its links.

What the interviewer will push on

"Why do you need the map?" Two reasons — it terminates the cycles, and it keeps shared nodes shared. Say both; most candidates give only one.

"Why register the copy before recursing?" Otherwise a cycle re-enters a node that is not yet in the map and recurses forever.

"What are the map keys?" The original node objects, compared by identity.

"What if the graph is disconnected?" The problem promises it is connected. If not, you would loop over all nodes and clone from each unvisited one — exactly the outer loop of 4.20.1.

"BFS or DFS?" Either. BFS avoids the stack depth risk.

One thing to volunteer: connect it to JSON.stringify throwing on circular references. It shows the problem is a real one that real tools have to solve.

Next: 4.20.3 Max Area of Island — the flood fill from 4.20.1, returning a number.