Clone Graph

The problem

You are given node, one node of a graph. Each node has a number, val, and a list, neighbors, of the nodes joined to it. Joins go both ways, and every node can be reached from node. Make a deep copy: one new node for each original node, with the same val, whose neighbors are the matching new nodes, never originals. Return the new node that matches node, and leave the original unchanged. For an empty graph, given as null, return null. The examples name each node by its val and list the neighbors of node 1, then node 2, and so on. node is node 1.

What to write

Implement solve using the node objects described above. The judge constructs the objects from the serialized examples.

type GraphNode = {val:number;neighbors:GraphNode[]};

function solve(node: GraphNode | null): GraphNode | null

Input
adjList = [[2,4],[1,3],[2,4],[1,3]]

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

Input
adjList = [[]]

Output
[[]]

Constraints

The graph is connected or empty.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every join goes both ways: in the first example node 1 lists node 2, and node 2 lists node 1. So following neighbors will bring you back to nodes you have already met, again and again. Every node can be reached from the one you are given, so one starting point is enough.

2. Hint 2: Ask a smaller question

   Take the smallest graph with a join: nodes 1 and 2, each listing the other. You make a new node for 1, go to its neighbor and make a new node for 2. The new 2 must list the new 1. Where do you get that node from, without making another one?

3. Hint 3: Name the pattern

   The joins lead round in circles, yet every node must be copied once. That is the signal for a graph traversal with a visited set: walk along the neighbor lists and remember the nodes already handled. The memory is a hash map, a table that finds a key's entry in about one step, from each original node to its copy. Read the lesson on graph traversal with a visited set.

4. Hint 4: State the invariant

   A node is in the map from the moment its copy is made, before any of its neighbors is visited. So each original node gets exactly one copy, and whenever the walk comes back to a node, the copy is already there to be reused.

5. Hint 5: Sketch the pseudocode

   Make an empty map. clone(original): if original is in the map, return its entry. Otherwise make a new node with the same value, store it in the map under original, then add clone(neighbor) to the new node's list for each neighbor of original, and return the new node. The answer is null if node is null, otherwise clone(node).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Memoize a new node before exploring its neighbors so cycles resolve to already-created copies.

The slow way

Copy a node by making a new node and then copying each of its neighbors the same way. With no memory of what was copied, this never ends: node 1 copies its neighbor 2, node 2 copies its neighbor 1, and so on, with a fresh node every time. Even two joined nodes stop the program with an error about calls nested too deep.

The insight

Walking the graph is not the problem; forgetting is. Write down, for every original node, the copy you made for it. Then meeting a node a second time is harmless: you look up its copy and use that. The same record tells you when to stop walking and which new node to connect to.

Step by step

1. Keep a map from each original node to its copy. The map is a hash map: a table that finds the entry for a key in about one step. It answers two questions at once: was this node copied already, and which new node stands for it?
2. A node that was copied before: return the copy it already has. This is what stops the walk from going round a ring for ever. It also makes two nodes that share a neighbor connect to the same new node instead of two different ones.
3. Otherwise make its copy and record it in the map straight away. The copy goes into the map before any neighbor is visited. A neighbor's own list leads back to this node, and by then the map must already hold this node's copy.
4. Copy each neighbor the same way to fill the copy's neighbor list. The function calls itself on each neighbor and collects what comes back: a copy made earlier, or a new one. The list keeps the order of the original's list.
5. Return the copy with its neighbor list filled in. Whoever asked for this node, the start or a neighbor, receives the new node and can put it in its own list.
6. An empty graph has no node to copy; otherwise copy from the given node. A null input has no value and no neighbors to read, so it is answered with null directly. Otherwise one call on the given node copies everything, because every node can be reached from it.

The same numbered steps are the comments in each solution.

function solve(node) {
  // 1. Keep a map from each original node to its copy
  const copies = new Map();
  function clone(n) {
    // 2. A node that was copied before: return the copy it already has
    if (copies.has(n)) return copies.get(n);
    // 3. Otherwise make its copy and record it in the map straight away
    const copy = { val: n.val, neighbors: [] };
    copies.set(n, copy);
    // 4. Copy each neighbor the same way to fill the copy's neighbor list
    copy.neighbors = n.neighbors.map(clone);
    // 5. Return the copy with its neighbor list filled in
    return copy;
  }
  // 6. An empty graph has no node to copy; otherwise copy from the given node
  return node ? clone(node) : null;
}

type GraphNode = { val: number; neighbors: GraphNode[] };
function solve(node: GraphNode | null): GraphNode | null {
  // 1. Keep a map from each original node to its copy
  const copies = new Map<GraphNode, GraphNode>();
  function clone(n: GraphNode): GraphNode {
    // 2. A node that was copied before: return the copy it already has
    if (copies.has(n)) return copies.get(n)!;
    // 3. Otherwise make its copy and record it in the map straight away
    const copy: GraphNode = { val: n.val, neighbors: [] };
    copies.set(n, copy);
    // 4. Copy each neighbor the same way to fill the copy's neighbor list
    copy.neighbors = n.neighbors.map(clone);
    // 5. Return the copy with its neighbor list filled in
    return copy;
  }
  // 6. An empty graph has no node to copy; otherwise copy from the given node
  return node ? clone(node) : null;
}

def solve(node):
    # 1. Keep a map from each original node to its copy
    copies = {}

    def clone(original):
        # 2. A node that was copied before: return the copy it already has
        if original in copies:
            return copies[original]
        # 3. Otherwise make its copy and record it in the map straight away
        copy = GraphNode(original.val)
        copies[original] = copy
        # 4. Copy each neighbor the same way to fill the copy's neighbor list
        copy.neighbors = [clone(neighbor) for neighbor in original.neighbors]
        # 5. Return the copy with its neighbor list filled in
        return copy

    # 6. An empty graph has no node to copy; otherwise copy from the given node
    return clone(node) if node else None

Example 1, traced

Input
adjList = [[2,4],[1,3],[2,4],[1,3]]

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

Why it works

Each original node gets exactly one copy: the map is checked before a copy is made and filled the moment it is made. Each copy's list is built from the copies of the original's neighbors, in the same order. So the new nodes are joined exactly like the originals, no new node points at an original, and the original is only read.

Time and space

Time O(V + E), extra space O(V + E). V counts the nodes and E the joins. The function runs once for every entry of every neighbor list, two per join, plus once for the start: O(V + E) time. The map, the new nodes with their lists and the unfinished calls take O(V + E) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Record the copy in the map before you visit its neighbors. Recorded afterwards, a neighbor comes back to a node the map does not know yet and copies it again, until the program fails with calls nested too deep.
• A node met before must not be skipped: its copy still belongs in the list. If only new neighbors are added, the four lists of the first example come back as 2, then 3, then 4, then nothing.
• Do not put original nodes into a copy's list, for instance by reusing the original's list. The checker follows every join of your answer and rejects it with the message "Return a graph made of fresh nodes."

Pattern

Graph traversal with a visited set. Builds on Copy List With Random Pointer and Number of Islands.

Keep going