Problem overview
The method cloneGraph(node: Node): Node receives node 1 of a connected, undirected graph and returns a deep copy of the whole graph: the copy of node 1. The graph has n nodes numbered 1 to n, and node i has the value i. The lesson provides the Node class: it has a var field val of type Int and a var neighbors, a mutable.ArrayBuffer[Node] that starts empty.
A deep copy is made of exactly n brand-new nodes, one per original node, with the same values. The neighbour list of each new node holds the new nodes of the original node's neighbours, in the same order. No node of the copy may be a node of the original graph. For an empty graph the method receives null and returns null.
The examples write a graph as adjacency lists, where the list at position i - 1 holds the values of node i's neighbours. For [[2, 4], [1, 3], [2, 4], [1, 3]], a square of four nodes, the copy has the same shape. After running the method on it, walking the copy from the returned node prints [[2, 4], [1, 3], [2, 4], [1, 3]], and none of the four nodes is a node of the original. For a single node with no neighbours, [[]], the copy is one new node. For the empty graph the result is null.
Approach: one copy per node, found through a map
Copying a node's value is easy. Copying its neighbours is the problem: they point back, so a graph with a cycle would send a naive copy around the cycle forever, and a node reached by two routes would be copied twice.
The fix is a map from each original node to its copy. A node's copy is made the first time the search meets the node, and that is also when the node joins a queue. When a node leaves the queue, the copies of its neighbours are appended to its copy's neighbour list. A node that already has a copy is never copied or queued again, which also stops the search from circling a cycle.
This is a breadth-first search. Every node enters the queue once, and each edge is looked at twice, once from each end, so the work is proportional to nodes plus edges.
A recursive depth-first search with the same map works too. The queue version keeps the call stack flat, which matters for a long chain such as 50,000 nodes in a row. The method copies such a chain correctly: the copy has 50,000 nodes.
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, an emptymutable.HashMap[Node, Node]. It maps each original node to its copy. - Put the first entry in:
copies(node) = new Node(node.`val`). The map both finds the copy of any node met so far and tells which nodes have been met. - Create the queue
queue, an emptymutable.Queue[Node], for nodes whose neighbours still have to be copied. - Enqueue
node. Every node in the queue already has its copy. What the copy still lacks is its neighbour list, which is filled when the node leaves the queue. - Loop while
queue.nonEmpty. The search ends when every reachable node, which here means every node, has been taken from the queue. - Dequeue the node at the front into
current. Now its copy's neighbour list gets filled. - Loop over
current.neighborswithneighbor. - Check
!copies.contains(neighbor). On a map,containslooks at the keys. No copy yet means this is the first time the search meets the node. - Make the copy:
copies(neighbor) = new Node(neighbor.`val`). This is the one moment this node's copy is made. - Enqueue
neighborso its own neighbours get copied when it leaves the queue. A node joins the queue only when its copy is made, so each node is queued exactly once. - Link the copies after the
if, still inside the loop:copies(current).neighbors += copies(neighbor). The copy ofcurrentpoints to the copy ofneighbor, never toneighboritself. The neighbours arrive in the original order, so each copied list keeps that order. - Return
copies(node)as the last expression: the copy of node 1.
The solution in Scala
class Solution {
def cloneGraph(node: Node): Node = {
if (node == null) {
return null
}
val copies = mutable.HashMap[Node, Node]()
copies(node) = new Node(node.`val`)
val queue = mutable.Queue[Node]()
queue.enqueue(node)
while (queue.nonEmpty) {
val current = queue.dequeue()
for (neighbor <- current.neighbors) {
if (!copies.contains(neighbor)) {
copies(neighbor) = new Node(neighbor.`val`)
queue.enqueue(neighbor)
}
copies(current).neighbors += copies(neighbor)
}
}
copies(node)
}
}
The Scala details worth a closer look:
valis a keyword, so the field is written with backticks:node.`val`. The same backticks appear innew Node(node.`val`).- Identity, not value, is the key.
Nodedoes not defineequalsorhashCode, so two nodes are equal only when they are the same object. Two different nodes both holding 1 are different keys:new Node(1) == new Node(1)isfalse, and a map given both as keys has size 2. That is what the algorithm needs. copies(node) = ...on amutable.HashMapinserts or replaces an entry. Readingcopies(neighbor)for a missing key would throw, which is why the code checkscontainsfirst. Every read happens after the copy exists.mutable.Queueprovidesenqueueto add at the back anddequeue()to remove from the front. The lesson providesmutable; in a file of your own, addimport scala.collection.mutable.+=on anArrayBufferappends an element. Becauseneighborsis avarholding a mutable buffer,+=changes the buffer in place.nulland==.node == nullis safe on anullreference in Scala, and it is the check the empty graph needs. The earlyreturnsits outside any loop, so it is an ordinary one.
Complexity
Let V be the number of nodes and E the number of edges.
Time: O(V + E). Each node is queued once. When a node leaves the queue, its neighbour list is scanned once, and over the whole run each edge is scanned twice. Map and queue operations take constant time on average.
Space: O(V) extra. The map holds one entry per node, and the queue holds at most all of them. The copy itself, V nodes and E links, is the output.
Edge cases and common mistakes
- The empty graph.
nullin,nullout. Without the first check, readingnode.`val`would throw aNullPointerException. - A single node. The loop runs once, finds no neighbours, and the result is a new node with an empty list.
- Cycles. In the square, node 1's copy is linked to the copies of 2 and 4, and later those link back to 1's copy. The map is what makes them point to the same new node and not to new duplicates.
- Linking to the original. Writing
copies(current).neighbors += neighborwould build a copy that points into the original graph. The printed values would look right while the copy shared nodes with the original, which the tests check. - Making the copy later than the enqueue. Every node needs its copy at the moment it joins the queue, because the linking line reads
copies(neighbor)straight away. - Losing the order. Neighbours must be appended in the original order. The loop does this because it walks
current.neighborsfrom the start. A copy of[[3, 2], [1, 3], [2, 1]]keeps node 1's neighbours as 3 then 2. - Using values as keys. The values are unique here, so a map from
InttoNodewould also work, but mapping nodes to nodes is the form that works for any graph.
Testing
[[2, 4], [1, 3], [2, 4], [1, 3]]copies to[[2, 4], [1, 3], [2, 4], [1, 3]]with no shared nodes.[[]]copies to[[]].[], the empty graph, givesnull.[[2, 3], [1], [1]]copies to[[2, 3], [1], [1]].[[3, 2], [1, 3], [2, 1]]copies to[[3, 2], [1, 3], [2, 1]].
