Clone Graph

The problem

You are given one node of a connected, undirected graph. Each node has a value val and a list of its neighbors. Return a deep copy of the graph: a brand new node for every node, joined by the same edges. No node of the copy may be a node of the original.

The values are 1, 2, 3 and so on, one per node. The input is written as an adjacency list: line i lists the neighbors of node i. You are handed node 1, and you return the copy of node 1.

Example 1

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

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

Four nodes with edges 1–2, 1–3, 2–3 and 3–4. The copy has the same shape, built from four new nodes.

Example 2

Input: adjList = [[]]

Output: [[]]

One node with no neighbors. Its copy is one new node with no neighbors.

Example 3

Input: adjList = []

Output: []

The graph is empty, so the node is null and so is the copy.

Constraints

• 0 ≤ number of nodes ≤ 100 (call it V; call the number of edges E)
• Node values are 1 to V, all different.
• No edge joins a node to itself, and no edge appears twice.
• The graph is connected.

Clarifying questions

Can the graph have cycles?

Yes. Every undirected edge is already a small cycle: 1 lists 2, and 2 lists 1. The copy must not loop forever.

Must the neighbor order stay the same?

Yes. Copy each list in the same order, so the adjacency lists match.

Can the input be null?

Yes, for an empty graph. Return null.

Is every node reachable from the one we get?

Yes. The graph is connected, so one search from that node finds them all.

Spot the pattern

To copy every node we must visit every node, by following edges from the one we are given. That is graph search. The hard part is that edges lead back to nodes we have already met. So, as in every graph search, we keep a record of what we have seen. Here the record is a map from an original node to its copy, which also tells us which copy to link to.

Solutions

DFS with a mapO(V + E)

Show all

There is only one approach worth showing. Every node and every edge must be copied, so no method can do less than O(V + E). Breadth-first search with the same map costs the same.

DFS with a map O(V + E)

The idea

Write clone(original), which returns the copy of original.

• If original is already in the map, its copy exists. Return it.
• Otherwise, make a new node with the same value, and put it in the map right away. Then, for each neighbor in order, call clone on it and add the result to the new node’s neighbors.

Saving the copy before the loop is the key step. When a neighbor leads back to original, the map already holds its copy, so the call returns at once instead of starting over.

Why it is correct: each node gets exactly one copy, because a copy is made only when the map has none. Each copy gets the copies of the same neighbors, in the same order. So the copy has the same nodes and the same edges.

Walkthrough

copies

empty

call stack top →

empty

1. copies = {}
2. def clone(original):
3. if original in copies: return copies[original]
4. copy = Node(original.val)
5. copies[original] = copy
6. for neighbor in original.neighbors:
7. copy.neighbors.append(clone(neighbor))
8. return copy
9. return clone(node) if node else None

The original graph is on the left. Its copy will grow on the right. The map "copies" remembers which node already has a copy.

← BackStep →Play1 / 15

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

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

    // Depth-first search with a map from each original node to its copy.
    // Every node is copied once and every edge is followed once.
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        // Already copied: reuse the copy, so a cycle does not loop forever.
        if (copies.containsKey(node)) return copies.get(node);
        Node copy = new Node(node.val);
        // Save the copy before visiting neighbors, because they may point back here.
        copies.put(node, copy);
        for (Node neighbor : node.neighbors) copy.neighbors.add(cloneGraph(neighbor));
        return copy;
    }
}

Big O

Time O(V + E)Space O(V)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion, so we count the calls of clone. A call that finds the map entry does a fixed job. A call that makes a copy does a fixed job plus one loop run per neighbor, and each loop run starts one more call. So each call counts as 1 step, and the loop runs are the calls it starts.

   1. copies = {}
   2. def clone(original):
   3. if original in copies: return copies[original]
   4. copy = Node(original.val)
   5. copies[original] = copy
   6. for neighbor in original.neighbors:
   7. copy.neighbors.append(clone(neighbor))
   8. return copy
   9. return clone(node) if node else None

2. 2 Count the runs on Example 1

   The table counts, for each node, how many times clone was called on it. Node 1 is called once at the start, and once from each of its 2 neighbors. Every other node is called once from each neighbor.

   3 + 2 + 3 + 1 = 9 calls. Each node was copied only once.

   	node 1	node 2	node 3	node 4
   neighbors	2	2	3	1
   clone() calls on it	3	2	3	1
   copies made	1	1	1	1

   total

   3 + 2 + 3 + 1 = 9 calls

3. 3 Write the count for any n

   A node is copied once, so its neighbor loop runs once. Over all nodes, the loops run once per neighbor listing. Each undirected edge is listed twice, once at each end, so that is 2 × E runs, each starting one call. Add the first call:

   1 + 2 × E calls, plus V copies made

   Check it with Example 1: E = 4, so 1 + 8 = 9 calls, and V = 4 copies. That matches the table.

4. 4 Keep only the part that grows fastest

   Drop the 1 and the 2. What is left is V + E: the size of the graph. We keep V too, because a graph can have more nodes than edges, like the single node of Example 2.

   So the time is O(V + E).

5. S Space: count the extra memory the same way

   The map holds one entry per node: V entries. The call stack can be V calls deep, if the graph is a long path. The copy itself is the answer, so it is not counted. So the extra space is O(V).

   copies map (V entries)call stack (up to V deep)

Common mistake

Saving the copy after the neighbor loop

If the copy goes into the map only after its neighbors are done, the first neighbor calls back into the same node, finds no entry, and makes a second copy. That copy calls back again, and the recursion never ends.

Tested at the limits

2,000 random connected graphs of 0 to 8 nodes, from a single line to every pair joined, with the neighbor lists in random order. Every time, the DFS with a map built a copy with the same values and the same neighbors in the same order as the original, used no original node, and left the original unchanged.

Largest inputs	Result
100 nodes with every pair joined (the most allowed), 4,950 edges. DFS with a map.	Under 0.01 s, and about 0.3 MB of extra memory: the map holds 100 copies, and the copies hold all 9,900 neighbor links.
A line of 100 nodes, so the search goes 100 calls deep. DFS with a map.	Under 0.01 s, and about 0.06 MB of extra memory. 100 calls is far below the Python limit of 1,000.