Problem overview
The method cloneGraph receives node, node 1 of a connected, undirected graph, or null when the graph is empty. Each node holds a value val and a list neighbors. The lesson provides the Node class, shown in the starter code's comment, with exactly those two fields and a constructor that takes the value. The method must return a deep copy: the copy of node 1, in a graph of brand-new nodes with the same values, where each new node's neighbor list holds the new nodes of the original's neighbors, in the same order. No node of the copy may be a node of the original.
The examples show a graph by its adjacency lists. For [[2, 4], [1, 3], [2, 4], [1, 3]], four nodes are joined in a square: node 1 is next to 2 and 4, node 2 to 1 and 3, and so on. The copy has the same shape, built from 4 new nodes. For [[]] the graph is a single node without neighbors, and for [] the function gets null and returns null.
The statement asks for O(V + E) time and O(V) extra space, where V is the number of nodes and E the number of edges.
Approach: one copy per node, found through a Map
Copying one node is easy: new Node(node.val). The difficulty is the neighbor lists. A node's copy must point to the copies of its neighbors, and those neighbors point back, so the graph is full of cycles. Two rules solve it:
- Keep a
Mapfrom each original node to its copy. When the search meets a node, the map says whether it already has a copy, so a node is never copied twice. - A copy's neighbor list is filled by looking up the copies of the original's neighbors in the map, never by reusing the original nodes.
The walk is a breadth-first search. A node's copy is created the first time the node is met, and that is also when it joins the queue. When a node leaves the queue, its neighbors' copies are appended to its copy's list. The map is also what stops the search from going around a cycle forever. Since the graph is connected, the search reaches every node from node 1.
A recursive DFS with the same map works as well. On a graph with 50,000 nodes in a long chain, a BFS with a queue has no call-stack depth to worry about.
In the run for the square graph, the copy has 4 nodes, none of them nodes of the original, and the neighbor lists read [[2, 4], [1, 3], [2, 4], [1, 3]], like the input.
Step by step
- Handle the empty graph. If
node === null, returnnull. The next lines readnode.val, which needs a node. - Create
copiesasnew Map<Node, Node>(). AMapcan use objects as keys and compares them by identity, so two different nodes are two different keys even when their values are equal. - Put in the first entry:
nodemapped tonew Node(node.val). - Create
queueas aNode[]holding justnode. The nodes in the queue already have their copies; what their copies still lack is the neighbor list. - Declare
headwithlet, at 0: the index of the next node to take. Moving an index forward is cheaper thanshift(), which moves every remaining element each time. - Loop while
head < queue.length. Some nodes are still waiting. - Take
queue[head]intocurrent. - Do
head++. The earlier entries stay in the array but are never read again. - Loop over
current.neighborswithfor...of. Over the whole run each edge is looked at twice, once from each end. - Test
!copies.has(neighbor). No copy means this is the first time the search meets this node. - Make its copy:
copies.set(neighbor, new Node(neighbor.val)). This is the only moment this node's copy is made. - Push
neighborontoqueue. Its own neighbors get copied when it leaves the queue. Because a node joins the queue only when its copy is made, each node is queued once. - Link the copies after the
if, still inside thefor: pushcopies.get(neighbor)ontocopies.get(current).neighbors. The copy ofcurrentpoints to the copy ofneighbor, never toneighboritself, and the order ofcurrent.neighborsis kept. - Return
copies.get(node), the copy of node 1.
The solution in TypeScript
class Solution {
cloneGraph(node: Node | null): Node | null {
if (node === null) {
return null;
}
const copies = new Map<Node, Node>();
copies.set(node, new Node(node.val));
const queue: Node[] = [node];
let head = 0;
while (head < queue.length) {
const current = queue[head];
head++;
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);
}
}
Some TypeScript details:
Node | nullis a union type: the parameter is a node ornull. The checknode === nulluses strict equality, and after it returns, the rest of the method can usenodeas aNode.- Objects as
Mapkeys.Mapcompares keys by identity. In a test with two different nodes that both have the value 1, the map keeps two entries, and each key finds its own value. A plain object can't do this: its keys are strings, so both nodes turn into the same key,"[object Object]", and the second assignment overwrites the first. Map.getcan returnundefined. It does when the key is missing. In this method every node has a copy before it is looked up, socopies.get(current)andcopies.get(neighbor)always find one.new Map<Node, Node>()gives the type arguments for the keys and values. They exist only for the compiler and are erased at run time.constand mutation.queueis aconst, yetqueue.push(...)is fine:conststops reassigning the name, not changing the array.headchanges, so it useslet.
Complexity
Time: O(V + E). Each node is created once, queued once and taken from the queue once. Each edge is looked at twice, once from each end. The Map operations are constant time on average.
Space: O(V) extra. The map and the queue each hold one entry per node. The copy itself, which is the output, also takes O(V + E).
Edge cases and common mistakes
- The empty graph.
nullin,nullout. Without the first check,node.valwould fail onnull. - A single node.
[[]]gives one new node with an empty neighbor list. The loop takes that node, finds no neighbors and ends. - Cycles. In the square graph, node 1 leads to 2, 2 leads to 3, 3 leads to 4 and 4 leads back to 1. The
hascheck is what makes the search stop instead of running forever. - Linking to the original. Pushing
neighborinstead ofcopies.get(neighbor)would make the copy point into the original graph, which the statement forbids. - Copying a node twice. Making a new
Nodewithout checking the map would create several copies of one node, and the copied graph would stop matching the original's shape. - Linking only the first time. The link step must run for every neighbor, not just for new ones. Otherwise the edges that lead to already-copied nodes are lost.
- Neighbor order. The neighbors are visited in the original's order, so each copied list keeps it. For nodes whose neighbors are
[3, 2],[1]and[1], the copy's lists read[[3, 2], [1], [1]]. - Using a plain object as the map. Its keys are strings, so different nodes can collide.
Testing
[[2, 4], [1, 3], [2, 4], [1, 3]]gives a copy with the same lists, built from 4 new nodes.[[]]gives one new node without neighbors.[]givesnull.[[2], [1, 3], [2]], a chain of three, gives[[2], [1, 3], [2]].- A chain of 50,000 nodes is copied completely: all 50,000 nodes are in the copy.
