LeetCode 133 · Medium · Graphs

Clone Graph

Given one node of a connected undirected graph, return a deep copy of the whole graph: brand-new nodes with the same values, wired to each other exactly as the originals are.

O(V + E)time
O(V)space
DFS + hash mapold node → its copy

list i holds the neighbours of node i + 1 · 0–8 nodes · edges go both ways · connected

original

clone

oldToNew original → copy

Call stack bottom → top

private Map<Node, Node> oldToNew = new HashMap<>();public Node cloneGraph(Node node) { if (node == null) { return null; } return dfs(node);}private Node dfs(Node node) { if (oldToNew.containsKey(node)) { return oldToNew.get(node); // copied already } Node copy = new Node(node.val); oldToNew.put(node, copy); // before the neighbours for (Node nei : node.neighbors) { copy.neighbors.add(dfs(nei)); } return copy;}
node
—
nei
—
copy.neighbors
—
oldToNew.size()
0

Why it works

  1. Copying naively (make a node, then copy each neighbour recursively) never stops on a cycle: 1 copies 2, 2 copies 1 again, and so on. It would also make several copies of the same node.
  2. The map is both the visited set and the answer. oldToNew says whether a node has a copy and hands it back, so every original gets exactly one copy and every edge is wired to that copy.
  3. O(V + E): each node is copied once, and each adjacency entry (two per undirected edge) costs one dfs call that is either an O(1) lookup or the first visit. The map and the recursion take O(V).
  4. Pitfall: store the copy in the map before looping over the neighbours. If you store it after, the neighbour's dfs cannot find it and the cycle 1 → 2 → 1 recurses forever.
  5. Variant: BFS works the same way: create the copy when a node is first queued, and wire edges as you pop. Copy List with Random Pointer (138) uses the same old → new map.