Clone Graph

You are given a reference to one node of a connected, undirected graph. Every node has an integer val and a list neighbors of the nodes it is connected to. Return a deep copy of the whole graph: a reference to the copy of the given node, where every node is a brand-new object and the copies are connected exactly like the originals. No copy may point back into the original graph.

In the tests, a graph is written as an adjacency list: entry i (0-based) lists the neighbours of the node whose value is i + 1. The node you receive is always the one with value 1. An empty list means there is no graph, and you receive null.

Example 1

Example 2

Example 3

Constraints

• The graph has between 0 and 100 nodes.
• Node values are unique and equal to their 1-based position: 1, 2, ..., n.
• The graph is undirected and connected, with no self-loops and no repeated edges.

Pattern Path · Graphs: Traversal · problem 130 of 169

Start simple

There is no meaningfully slower correct approach; the naive mistake is recursing without remembering copied nodes, which never terminates on a cycle.

The key idea

A graph can contain cycles and nodes reachable along several paths, so a plain recursive copy would either loop forever or create several copies of the same node. The fix is a dictionary copies from each original node to its clone. It guarantees one clone per original and tells you whether a node has been seen.

Run BFS from the given node. Clone the start node, put it in the map and the queue. For each node you pop, look at every neighbour: if it has no clone yet, create one, store it, and enqueue the original so its own edges get processed later. Either way, append the neighbour's clone to the current node's clone's neighbour list.

Each original node is enqueued exactly once (the map check prevents repeats), and each edge entry is examined once from each side, so every neighbour list in the copy ends up in the same order as in the original. A recursive DFS with the same map works just as well.

Complexity

• Time: O(V + E)
• Space: O(V) for the map and the queue

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if node is None:
            return None
        copies = {node: Node(node.val)}  # original node -> its clone
        queue = deque([node])
        while queue:
            current = queue.popleft()
            for neighbor in current.neighbors:
                if neighbor not in copies:
                    copies[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                copies[current].neighbors.append(copies[neighbor])
        return copies[node]

JavaScript

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */
var cloneGraph = function(node) {
  if (node === null) return null;
  const copies = new Map([[node, new Node(node.val)]]); // original -> clone
  const queue = [node];
  for (let i = 0; i < queue.length; i++) {
    const current = queue[i];
    for (const neighbor of current.neighbors) {
      if (!copies.has(neighbor)) {
        copies.set(neighbor, new Node(neighbor.val));
        queue.push(neighbor);
      }
      copies.get(current).neighbors.push(copies.get(neighbor));
    }
  }
  return copies.get(node);
};

What the interviewer is checking

It tests whether you can traverse a graph that has cycles and preserve its shape, using a hash map from original to copy as the core idea.

Mistakes to avoid

• Forgetting the empty-graph case (null input).
• Marking a node as visited only when it is popped, which can create two clones of the same node.
• Returning the original node or reusing original neighbour objects instead of their clones.

Follow-ups to expect

• Can you do it recursively? (DFS with the same memo map.)
• What if the graph is directed or disconnected? (Same idea; clone from every component.)
• How would you copy a linked list with random pointers? (Same old-to-new map.)

In real software

Deep-copying object graphs, such as duplicating a document with cross-references, structured cloning in browsers, or snapshotting game state, relies on the same original-to-copy map to keep shared references and cycles intact.

Practice next