Problem Statement

Clone Graph

A graph is a set of nodes connected by lines. Each node holds a value and a list of its neighbors, which are the other nodes it links to directly. You are handed one node from a connected undirected graph. "Connected" means you can reach every node by walking from neighbor to neighbor, and "undirected" means a link goes both ways, so if A points to B, then B also points to A. Your job is to make a deep copy of the whole graph. A deep copy means brand new nodes, not the originals, with the same values and the same connections wired up between the new ones.

mediumGraphsGraphsTime: O(V + E) · Space: O(V)

Signals to notice

deep copy a graphhandle cyclesmap original to clone

Brute force first

No simpler alternative — you must handle cycles in any approach. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

BFS or DFS with a hash map from original node → cloned node. When you encounter a node already in the map, reuse the clone instead of creating a new one. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `adjList=[[2,4],[1,3],[2,4],[1,3]] (4 nodes; node1~2,4 | node2~1,3 | node3~2,4 | node4~1,3); start at node1`

dfs(1): not in cloned -> copy1=Node(1), cloned={1:c1}; recurse neighbors [2,4]
dfs(2): not in cloned -> copy2=Node(2), cloned={1,2}; recurse neighbors [1,3]
dfs(1): already in cloned -> return c1; c2.neighbors=[c1], next neighbor 3
dfs(3): new -> c3=Node(3), cloned={1,2,3}; neighbors [2,4] -> dfs(2) returns c2; dfs(4)
dfs(4): new -> c4=Node(4), cloned={1,2,3,4}; neighbors [1,3] -> c1, c3 already cloned -> c4.neighbors=[c1,c3]
back in dfs(3): c3.neighbors=[c2,c4]; back in dfs(2): c2.neighbors=[c1,c3]
back in dfs(1): neighbor 4 -> dfs(4) returns c4; c1.neighbors=[c2,c4]
return c1 -> full clone [[2,4],[1,3],[2,4],[1,3]]

What must stay true

The hash map guarantees each node is cloned exactly once. When you reach a node you've already cloned, you connect to the existing clone — this correctly handles cycles. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

cloned = {}                      # original node -> its clone
function dfs(n):
    if n in cloned: return cloned[n]   # reuse, breaks cycles
    copy = Node(n.val); cloned[n] = copy   # record BEFORE recursing
    for nb in n.neighbors: copy.neighbors.add(dfs(nb))
    return copy
return dfs(start) if start else None

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not handling cycles — without the visited map, a cycle causes infinite recursion or infinite queue growth. The map serves dual purpose: visited tracking and clone lookup. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Graphs Pattern