medium

Clone Graph

Make a deep copy of a graph that contains cycles by keeping a map from each original node to the single copy that stands for it.

1. Define the problem

Clone Graph

You are given a connected undirected graph. Make a deep copy of it: a brand new set of nodes with the same shape, where no new node points at any old node. Here the graph arrives as an adjacency list and the answer goes back as an adjacency list, so nothing awkward has to be passed around. Row i of the input holds the neighbours of node i + 1. Walk the graph once and keep a map from original node to its copy . Before copying a node, check the map. If the copy already exists, hand back the one you made earlier instead of making a second one. That is what stops the cycles from looping forever.

Constraints

  • 0 ≤ number of nodes ≤ 100
  • Node values are 1 to n and are all different
  • There are no repeated edges and no node is joined to itself
  • The graph is connected, so every node is reachable from node 1

Example

Inputadjacency = [[2, 4], [1, 3], [2, 4], [1, 3]]
Output[[2, 4], [1, 3], [2, 4], [1, 3]]

Explanation Node 1 is joined to 2 and 4, node 2 to 1 and 3, node 3 to 2 and 4, node 4 to 1 and 3. The copy has the same shape, so it prints the same.

2. Know the words first

In plain terms

Adjacency list
A way of writing a graph down: for each node, the list of nodes it is joined to. Row 0 here belongs to node 1, row 1 to node 2, and so on.
Deep copy
A copy where the contents are copied too, not just the outer shell. Changing the copy must never change the original.
Cycle
A path that comes back to where it started. Graphs with cycles are why a plain recursive copy would never stop on its own.
Memo map
A lookup that remembers work already done. Here it maps each original node to the single copy that stands for it.
3. Visualize the solution

One cell per node, value = whether a copy of that node exists yet

One cell per node, value = whether a copy of that node exists yet
Statusinit

Four nodes in a square, and no copies made yet.

What happens in this step

adjacency = [[2, 4], [1, 3], [2, 4], [1, 3]]
copies = empty map

Node 1 is joined to 2 and 4, node 3 is joined to 2 and 4.
It is a square, so the walk will run into itself.
Step 1 of 7

Steps to visualize

  1. The row has one cell per node of the original graph, labelled with the node number.
  2. The value says whether that node already has a copy stored in the map.
  3. The copy walk starts at node 1 and follows neighbours one at a time.
  4. Each time it reaches a node with no copy, it makes one and records it before going any deeper.
  5. When it reaches a node that already has a copy, it reuses that copy and turns back.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per node, value = whether a copy of that node exists yet
Statusinit

Four nodes in a square, and no copies made yet.

What happens in this step

adjacency = [[2, 4], [1, 3], [2, 4], [1, 3]]
copies = empty map

Node 1 is joined to 2 and 4, node 3 is joined to 2 and 4.
It is a square, so the walk will run into itself.
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function cloneGraph(adjacency) {
  if (adjacency.length === 0) return [];

  const nodes = adjacency.map((_, index) => ({ value: index + 1, neighbors: [] }));

  adjacency.forEach((list, index) => {
    for (const neighbor of list) {
      nodes[index].neighbors.push(nodes[neighbor - 1]);
    }
  });

  const copies = new Map();

  function clone(node) {
    if (copies.has(node.value)) {
      return copies.get(node.value);
    }

    const copy = { value: node.value, neighbors: [] };
    copies.set(node.value, copy);

    for (const neighbor of node.neighbors) {
      copy.neighbors.push(clone(neighbor));
    }

    return copy;
  }

  clone(nodes[0]);

  return adjacency.map((_, index) => {
    const copy = copies.get(index + 1);
    return copy ? copy.neighbors.map((neighbor) => neighbor.value) : [];
  });
}
Time
O(n + e), where e is the number of edges
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
adjacency = [[2, 4], [1, 3], [2, 4], [1, 3]][[2, 4], [1, 3], [2, 4], [1, 3]]example from the docstring, a four node square
adjacency = [[2], [1]][[2], [1]]two nodes joined by a single edge
adjacency = [[]][[]]one node with no neighbours at all
adjacency = [][]an empty graph, the degenerate case
adjacency = [[2, 3], [1], [1]][[2, 3], [1], [1]]a middle node with two leaves and no cycle
adjacency = [[2], [1, 3], [2]][[2], [1, 3], [2]]a straight line, so the walk has to back up twice

Keep reading