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

In plain English, we are given a reference to a node in a connected, undirected graph. We need to return a "deep copy" of the graph. A deep copy means we cannot just return the original nodes; we must instantiate completely new Node objects for every single node in the graph, and wire their neighbors arrays to point to the other newly created nodes, exactly mirroring the original graph's structure. The node values are unique and typically range from 1 to 100. An important edge case is an empty graph (null input), which should return null.

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 ELI5 Analogy

Think of building a precise replica of a tangled Lego model. You pick up a piece, look at what's attached to it, and start building. But wait—if you just blindly build whatever is attached, you'll hit a piece that connects right back to your starting piece. If you build another starting piece, you've ruined the shape. And you'll keep building forever in an endless loop! To solve this, you keep a "checklist" (our hash map). Every time you mold a new plastic piece, you write down: "Original Piece A -> New Piece A". Before you build anything, you check the list. If it's on the list, you just grab the one you already made and snap it on.

What about a Brute Force Approach?

A naive approach would be standard recursion: copy the current node, then recursively copy all its neighbors and append them. Why does this fail? Because graphs have cycles. Node 1 connects to Node 2, and Node 2 connects back to Node 1. The naive recursion would try to copy Node 1, which copies Node 2, which copies Node 1, which copies Node 2, resulting in an infinite loop (a StackOverflowError). Even in a Directed Acyclic Graph (DAG) with no cycles, a naive approach would duplicate shared nodes. If Node A and Node B both point to Node C, the naive approach creates two separate Node C's. The map prevents both infinite loops and unintended duplication.

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.

Code Walkthrough & Trace

Let's trace a tiny graph where Node 1 connects to Node 2, and Node 2 connects back to Node 1.

Step	Action	Map (old_to_new)	Return Value
1	dfs(Node1) called	{}
2	Create Copy1. Register it.	{Node1: Copy1}
3	Loop Node1's neighbors. Call dfs(Node2)	{Node1: Copy1}
4	dfs(Node2) starts. Create Copy2. Register it.	{Node1: Copy1, Node2: Copy2}
5	Loop Node2's neighbors. Call dfs(Node1)	{Node1: Copy1, Node2: Copy2}
6	dfs(Node1) starts. Finds Node1 in map!	{Node1: Copy1, Node2: Copy2}	Returns Copy1 (stops cycle!)
7	Back in dfs(Node2). Append Copy1 to Copy2.neighbors
8	dfs(Node2) finishes loop. Returns Copy2		Returns Copy2
9	Back in dfs(Node1). Append Copy2 to Copy1.neighbors
10	dfs(Node1) finishes loop. Returns Copy1		Returns Copy1

Key lines explained:

1. if cur in old_to_new: return old_to_new[cur] - This is our cycle-breaker and deduplicator. If we've seen it, give back the exact memory reference to the clone we already started building.
2. old_to_new[cur] = copy - We MUST do this before the for nei in cur.neighbors: loop. If we did it after, Step 6 in the trace would fail to find Node1 in the map, and we'd plunge into an infinite cycle.

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). To derive this: the dfs is called for every node, and inside it, we iterate over its neighbors. This means we process every node (O(V)) and we iterate over every edge connection (O(E)). Since O(V) hash map lookups and insertions are O(1), the total time scales linearly with the size of the graph.

O(V) space for the map, plus O(V) for the recursion or queue. The map stores exactly V entries. The call stack (for DFS) will go as deep as the longest path in the graph, which in the worst case (a straight line graph) is V. Thus, total auxiliary space is strictly bounded by O(V).

Edge Cases to Consider

• Empty Graph (Null input): Handled elegantly by the if not node: check at the very beginning.
• Single Node Graph (No edges): Works flawlessly. The loop for nei in cur.neighbors: will simply not execute, returning the copy immediately.
• Disconnected Graph: The problem explicitly states the graph is connected. But what if it wasn't? The current DFS only clones the connected component of the input node. To clone a fully disconnected graph, we would need a list of all nodes and iterate through them, calling dfs on any node not yet in our old_to_new map.

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.