Clone Graph

Why it belongs on this sheet

This is a strong graph question because it combines traversal with object reconstruction and cycle handling.

Pattern

Visited map from original to clone

Approach

Whenever you see a node for the first time, create its clone and store the mapping. Then recursively clone each neighbor and attach the cloned neighbors.

Java solution

import java.util.HashMap;
import java.util.Map;

class Solution {
  private final Map<Node, Node> copies = new HashMap<>();

  public Node cloneGraph(Node node) {
    if (node == null) {
      return null;
    }

    if (copies.containsKey(node)) {
      return copies.get(node);
    }

    Node copy = new Node(node.val);
    copies.put(node, copy);

    for (Node neighbor : node.neighbors) {
      copy.neighbors.add(cloneGraph(neighbor));
    }

    return copy;
  }
}

Complexity

• Time: O(V + E)
• Space: O(V)

Interview note

The map is not optional. Without it, cycles will blow up the recursion and duplicate nodes.