Problem overview
You get node, node 1 of a connected, undirected graph, and cloneGraph must return a deep copy of the whole graph: the copy of node 1. Node i has the value i, and every node reaches every other through its neighbors. A deep copy is made of exactly n brand-new nodes with the same values, and each new node's neighbor list 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 graph. An empty graph arrives as null and the function returns null.
The lesson provides the node class in a comment in the starter code, so you don't write it:
class Node(var `val`: Int) {
var neighbors: ArrayList<Node> = ArrayList()
}
The examples describe a graph by adjacency lists. In the first one, [[2, 4], [1, 3], [2, 4], [1, 3]], four nodes form a square: node 1 touches 2 and 4, node 2 touches 1 and 3, and so on. The copy has the same shape, built from four new nodes. A single node with no neighbors, [[]], copies to one new node, and the empty graph copies to null.
Approach
Copying a node is easy; the difficulty is the cycles. In the square, node 1 leads to 2, which leads to 3, then 4, then back to 1. A copy that blindly follows neighbors never stops, and a copy that makes a fresh node every time it meets one produces duplicates.
The fix is a HashMap 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 the queue. A node that already has a copy is never copied or queued again, which stops the search from circling forever and guarantees one copy per node.
The search is a breadth-first search. When a node leaves the queue, its copy still has an empty neighbor list. The search walks over the original node's neighbors, makes a copy for any neighbor that has none, and appends each neighbor's copy to the copy's list. Because the neighbors are visited in the original order, each copied list keeps that order.
A recursive DFS with the same map also works. This lesson uses a queue so that a long chain of nodes doesn't depend on the call stack.
Step by step
- Handle the empty graph. If
node == null, returnnull. After this check Kotlin knowsnodeis not null, so it can be used as aNodein the rest of the function. - Create the map.
HashMap<Node, Node>()maps each original node to its copy.Nodedoesn't defineequalsorhashCode, so the map compares nodes by identity: two different nodes are two different keys even when their values are equal. - Copy the first node.
copies[node] = Node(node.`val`). The field is namedval, a Kotlin keyword, so it is written in backticks. - Create the queue.
ArrayDeque<Node>()holds the nodes whose neighbors still need copying.addputs a node at the back andremoveFirsttakes the one at the front. - Queue the start.
queue.add(node). Every node in the queue already has its copy; what the copy lacks is its neighbor list. - Loop while the queue has nodes.
while (queue.isNotEmpty()). - Take the next node.
val current = queue.removeFirst(). - Visit its neighbors.
for (neighbor in current.neighbors). Over the whole run each edge is looked at twice, once from each end. - Test for a new node.
if (!copies.containsKey(neighbor))means the search meets this node for the first time. - Copy it.
copies[neighbor] = Node(neighbor.`val`). This is the only place a node's copy is made. - Queue it.
queue.add(neighbor), so its own neighbors are handled later. A node joins the queue only when its copy is made, so each node is queued once. - Link the copies. After the
if, add the neighbor's copy to the list of the current node's copy. The copy ofcurrentpoints to the copy ofneighbor, never toneighboritself.getValuereads both copies. - Return the start's copy.
copies[node]. The graph is connected, so every node was reached.
The solution in Kotlin
class Solution {
fun cloneGraph(node: Node?): Node? {
if (node == null) {
return null
}
val copies = HashMap<Node, Node>()
copies[node] = Node(node.`val`)
val queue = ArrayDeque<Node>()
queue.add(node)
while (queue.isNotEmpty()) {
val current = queue.removeFirst()
for (neighbor in current.neighbors) {
if (!copies.containsKey(neighbor)) {
copies[neighbor] = Node(neighbor.`val`)
queue.add(neighbor)
}
copies.getValue(current).neighbors.add(copies.getValue(neighbor))
}
}
return copies[node]
}
}
Kotlin details worth knowing:
- Nullable types. The parameter is
Node?and so is the return type, since both can benull. Afterif (node == null) return null, the compiler smart-castsnodetoNode. copies[key]versusgetValue(key). Reading a map with[]gives aNode?, because the key may be missing.getValue(key)gives a plainNodeand throws if the key is absent, which can't happen here because every neighbor in the loop has a copy by the time the line runs. The finalcopies[node]returns aNode?, which matches the return type.- Identity keys. A class that doesn't override
equalsandhashCodeuses object identity. TwoNode(1)objects are two separate keys in aHashMap; a test with two such nodes gives a map of size 2. That is what the algorithm needs. - Backticks.
valcan't be used as a plain name, so`val`is the way to declare and read it. ArrayDequehere is Kotlin's ownArrayDeque, so no import is needed.
Complexity
Each node is copied once and queued once, and each edge is examined twice, once from each end. That makes the time O(V + E), where V is the number of nodes and E the number of edges. The map and the queue hold at most V entries, so the extra space is O(V), not counting the copy itself.
Edge cases and common mistakes
- Empty graph. A
nullinput must givenull. Readingnode.`val`first would not compile, becausenodeis nullable. - Single node.
[[]]gives one new node and an empty neighbor list. The loop body never runs. - Returning the original node. Putting an original node into a copied list breaks the deep copy. A check on the square graph confirms that
cloneGraphreturns a different object, with none of the original nodes shared. - No map. Without it, a cycle makes the search loop forever, or the same node gets copied twice and neighbors point at different copies of the same node.
- Copying at dequeue time instead of at discovery time. A node can be found as a neighbor several times before it leaves the queue, so it could be copied more than once. The solution copies exactly when the node is first met.
- Forgetting order. Neighbors must be appended in the original order; iterating
current.neighborsin order does that. - Deep recursion. A graph can be a chain of 50,000 nodes. The queue-based version handles it; a recursive DFS goes that deep in the call stack.
Testing
Results from running the solution on graphs built from adjacency lists, printing the neighbor lists of the copy from node 1 up:
[[2, 4], [1, 3], [2, 4], [1, 3]]:[[2, 4], [1, 3], [2, 4], [1, 3]], with 4 copied nodes and none shared with the original[[]]:[[]][]:null[[2], [1, 3], [2]]:[[2], [1, 3], [2]][[3, 2], [1], [1]]:[[3, 2], [1], [1]], so the neighbor order is kept- A chain of 50,000 nodes: 50,000 copied nodes
