Clone Graph

Difficulty: Medium

You're given a reference to a node inside a connected undirected graph. Each node has a value and a list of neighbor nodes it's directly connected to.

Produce a deep copy of the entire graph: every node must be a brand new object (not the same one from the original graph), but the copied graph must have exactly the same structure - the same values, and the same connections between corresponding nodes.

Examples

Input: adjacency list = [[2,4],[1,3],[2,4],[1,3]] (node 1 connects to 2 and 4, node 2 connects to 1 and 3, etc.)
Output: [[2,4],[1,3],[2,4],[1,3]]

The copy has the same four nodes with the same connections, but every node object is a new one, distinct from the original.

Input: adjacency list = [[]]
Output: [[]]

A single node with no neighbors - the copy is a single new node, also with no neighbors.

Input: adjacency list = []
Output: []

An empty graph copies to an empty graph.

Approach

This is a graph traversal with one twist: instead of just marking a node "visited," you need to remember what its copy is, because other nodes' neighbor lists will need to point to that same copy later (and because the graph can have cycles, so you must avoid cloning any node twice).

The fix is a hash map from original node to cloned node. Traverse the graph (DFS or BFS, both work) starting from the given node. The first time you see a node, create its clone immediately and store it in the map before recursing into its neighbors - that way, if a neighbor loops back to a node you're already in the middle of cloning, you find its clone in the map instead of trying to clone it again. Once every node has been visited, walk through each original node's neighbor list and hook up the corresponding clones.

Solutions

DFS - Recursive with a Clone Map

Recursively visit each node. The first time a node is seen, create its clone and record it in the map right away, then recurse into its neighbors and attach each neighbor's clone (found or freshly created) to the current clone's neighbor list.

function cloneGraph(node) {
  if (!node) return null;

  const visited = new Map(); // original node -> cloned node

  function dfs(original) {
    if (visited.has(original)) {
      return visited.get(original);
    }

    const clone = { val: original.val, neighbors: [] };
    visited.set(original, clone);

    for (const neighbor of original.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }

    return clone;
  }

  return dfs(node);
}

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

BFS - Iterative with a Clone Map

Create the clone of the starting node up front, then use a queue to visit every original node exactly once. For each original node popped from the queue, walk its neighbor list: clone any neighbor not seen yet (and enqueue it), then link that neighbor's clone into the current node's clone.

function cloneGraph(node) {
  if (!node) return null;

  const visited = new Map();
  visited.set(node, { val: node.val, neighbors: [] });
  const queue = [node];

  while (queue.length > 0) {
    const current = queue.shift();

    for (const neighbor of current.neighbors) {
      if (!visited.has(neighbor)) {
        visited.set(neighbor, { val: neighbor.val, neighbors: [] });
        queue.push(neighbor);
      }
      visited.get(current).neighbors.push(visited.get(neighbor));
    }
  }

  return visited.get(node);
}

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