Problem overview
The method cloneGraph(node) receives node 1 of a connected, undirected graph and returns a deep copy of the graph: the copy of node 1. Each node holds a value, val, and an array of its neighbors, neighbors. The lesson provides the node class in a comment above the starter code, as the constructor function Node(val), which sets this.val and starts this.neighbors as an empty array. The graph has n nodes, node i has the value i, and every node can be reached from node 1.
A deep copy is made of exactly n brand-new nodes, one per original node, with the same values. The neighbor array of each new node holds the new nodes of the original node's neighbors, in the same order. No node of the copy may be a node of the original. When the graph is empty, node is null, and the method returns null.
For the square adjList = [[2, 4], [1, 3], [2, 4], [1, 3]], meaning 1 is joined to 2 and 4, 2 to 1 and 3, and so on, the copy has four new nodes joined in the same square. For [[]] the copy is one new node with no neighbors, and for [] the answer is null.
The lesson 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: a map from each original node to its copy
Copying one node is easy. The difficulty is the links. A node's neighbors link back to it, so the graph is full of cycles, and a naive recursive copy would copy node 1, then its neighbor 2, then 2's neighbor 1 again, and never stop. It would also create two copies of the same node.
The fix is a Map from each original node to its copy. It does two jobs: it finds the copy of any node met so far, and it tells which nodes have been met already. The search is a breadth-first search (BFS):
- A node's copy is made the first time the search meets the node. That is also the moment the node joins the queue.
- When a node leaves the queue, each of its neighbors is looked at. A neighbor without a copy gets one and is queued. Then the copy of the neighbor is appended to the neighbor array of the current node's copy.
A node that already has a copy is never copied or queued again, which is what stops the search from going around a cycle forever. A recursive DFS with the same map would also work.
The tests on this lesson walk the copy and check two things: that the neighbor lists have the right values in the right order, and that no node of the copy is a node of the original. For the square, the copy has the same lists, [[2, 4], [1, 3], [2, 4], [1, 3]], and shares none of the four nodes with the original.
Step by step
- Handle the empty graph. If
node === null, returnnull. The next lines read the node's value, which needs a node. - Create the map.
copies = new Map()maps each original node to its copy. AMapcan use objects as keys and compares them by identity, so two different nodes are two different keys even if their values were equal. A plain object can't do this, because its keys are strings. - Copy the first node.
copies.set(node, new Node(node.val)). The copy starts with an empty neighbor array. - Start the queue as an array holding just
node. Every node in the queue already has a copy; what its copy still lacks is its neighbor array. - Keep an index
head, declared withletand starting at 0, for the next node to take from the queue. Moving an index forward is cheaper thanshift(), which would move every remaining element each time. - Loop while
head < queue.length: some nodes are still waiting. - Take the current node,
queue[head], and then dohead++. - Loop over
current.neighborswithfor...of. Over the whole run each edge is looked at twice, once from each end. - If
!copies.has(neighbor), the search is meeting this node for the first time. Make its copy withcopies.set(neighbor, new Node(neighbor.val))and pushneighboronto the queue. This is the only place a copy is made, so each node is copied once and queued once. - Link the copies. Push
copies.get(neighbor)ontocopies.get(current).neighbors. The copy ofcurrentpoints to the copy ofneighbor, never to the original. The neighbors arrive in the order of the original array, so each copied array keeps the original order. - Return
copies.get(node), the copy of node 1. The graph is connected, so every node was reached.
The solution in JavaScript
class Solution {
cloneGraph(node) {
if (node === null) {
return null;
}
const copies = new Map();
copies.set(node, new Node(node.val));
const queue = [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);
}
}
JavaScript details worth knowing:
- Objects as keys. A
Mapkeeps the key as it is. With a plain object,o[a] = 1; o[b] = 2turns both nodes into the same string key"[object Object]", so the second assignment overwrites the first. Likewise,map.get({})isundefinedaftermap.set({}, 2), because the two{}are different objects. The lookups in this solution work because they use the very same node objects as keys. new Node(val).Nodeis a constructor function that the lesson provides. Calling it withnewmakes an object withvalset and an emptyneighborsarray. Each call makes a new array, so the copies don't share neighbor arrays.===withnull.node === nullis true only fornull. It's the right test here because the empty graph is passed asnull.- Reference types. Pushing
neighborinstead ofcopies.get(neighbor)would make a copy that points into the original graph. The array would look right when printed, but the lesson's tests would report nodes of the original in the copy.
Complexity
Time: O(V + E). Each node is copied once and queued once, and each edge is looked at twice, once from each end. Map operations take constant time on average.
Space: O(V) extra. The map and the queue each hold at most one entry per node. The copy itself, which is the output, takes O(V + E).
Edge cases and common mistakes
- The empty graph.
cloneGraph(null)must returnnull. Without the first check,node.valwould throw. - A single node.
[[]]gives a copy with value 1 and no neighbors, and the copy is a different object from the original. - Making copies at the wrong moment. Creating a copy every time a node is seen as a neighbor gives several copies of one node and breaks the links. A copy is created only when
copies.has(neighbor)is false. - Queuing nodes twice. Queuing a neighbor outside the
ifwould let the search loop around a cycle forever. - Returning the original. The method must return
copies.get(node), notnode. For the square graph, the returned node is a different object and none of the four nodes are shared. - A chain such as
[[2], [1, 3], [2]]. Node 2 is a neighbor of both 1 and 3, but gets exactly one copy, and both of its neighbors' copies link to it.
Testing
adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]gives a copy with the lists[[2, 4], [1, 3], [2, 4], [1, 3]]and no shared nodes.adjList = [[]]gives[[]], a single new node.adjList = []givesnull.adjList = [[2], [1, 3], [2]]gives[[2], [1, 3], [2]]with three new nodes.
