A ranking service clones a user’s social neighborhood so an experiment can shuffle edges without touching production. Each person node has a value and a neighbor list; the graph is undirected, so two people who follow each other list each other. The intern wrote new Node(val) and recursed into every neighbor. Two mutual follows in staging hung. They skipped a neighbor already on the call stack; staging returned, but A reached through B was a second node 1, and the experiment’s edge edits forked the graph.
Clone Graph asks for a deep copy of the connected component: one new node per original, every neighbor list holding clones, never originals. This is an interview writeup, not a layout lecture. The graphs post owns adjacency. The BFS post owns the queue. Here we only care about hashing original node objects to their clones so wiring a neighbor is a lookup, not a restart.
The problem
Given a reference to a node in an undirected graph, return a deep copy of the component that contains it: brand-new nodes, every neighbor on the copy a clone, never an original. Null copies as null; empty neighbors is legal. Identity is the node object, not val. Cycles are the point.
1 — 2
| |
4 — 3
start at 1 → a new 4-cycle of clones; clone(1).neighbors are copies of 2 and 4, never the originals
null → null
1, neighbors=[] → a new node 1 with an empty neighbor list
1 — 2
start at 1 → clones of 1 and 2, each listing the other copyThis problem’s node is Node with int val and List<Node> neighbors — not a TreeNode with left and right.
final class Node {
int val;
List<Node> neighbors;
Node(int val) {
this.val = val;
this.neighbors = new ArrayList<>();
}
}Note: Assigning clone.neighbors = orig.neighbors is a shallow list. The experiment still holds production nodes. Recursing copy(nei) with no dictionary on an undirected edge never returns.
Nested search for each neighbor is the honest brute force
A nested new Node per neighbor with no dictionary either hangs on the 2-cycle or, with a call-stack guard, forks a second clone of the same original. Cycles are the point; a DAG fixture in staging hid the fork.
The honest version that still refuses a HashMap: two parallel lists, scan for identity, and register the clone before walking neighbors so the back edge finds the same object. Correct. Quadratic.
Node cloneGraphNested(Node node) {
if (node == null) {
return null;
}
List<Node> origs = new ArrayList<>();
List<Node> copies = new ArrayList<>();
return copy(node, origs, copies);
}
Node copy(Node node, List<Node> origs, List<Node> copies) {
for (int i = 0; i < origs.size(); i++) {
if (origs.get(i) == node) {
return copies.get(i);
}
}
Node clone = new Node(node.val);
origs.add(node);
copies.add(clone);
for (Node nei : node.neighbors) {
clone.neighbors.add(copy(nei, origs, copies));
}
return clone;
}At a 4-node square this is a rounding error. On n nodes you may scan the whole list for every node and every neighbor: you paid a nested scan for a question a map answers in expected constant time per node: which clone did I already make for this original?
Map original to clone, then BFS-wire the neighbors
Same dictionary as copy list with random pointer: map original to copy, then wire jumps. Here the jumps are the neighbor list, and there is no single next chain to walk twice.
Create the start’s clone, put it in the map, offer the original. Poll. For each neighbor: on a miss, create, put, offer. Then always attach clones.get(nei) onto the current clone’s neighbor list. Put-and-offer on first sight so an undirected edge does not enqueue the same original twice.
start=1, neighbors [2, 4]
2 neighbors [1, 3]
4 neighbors [1, 3]
3 neighbors [2, 4]
put 1→1', queue [1]
poll 1
nei 2 miss put 2→2' offer 1'.neighbors += 2'
nei 4 miss put 4→4' offer 1'.neighbors += 4'
poll 2
nei 1 hit 2'.neighbors += 1'
nei 3 miss put 3→3' offer 2'.neighbors += 3'
poll 4
nei 1 hit 4'.neighbors += 1'
nei 3 hit 4'.neighbors += 3'
poll 3
nei 2 hit 3'.neighbors += 2'
nei 4 hit 3'.neighbors += 4'
return 1'The Java is that walk. The frontier is an ArrayDeque. Not java.util.Stack. Not ArrayList.remove(0).
Node cloneGraph(Node node) {
if (node == null) {
return null;
}
Map<Node, Node> clones = new HashMap<>();
Deque<Node> q = new ArrayDeque<>();
clones.put(node, new Node(node.val));
q.offer(node);
while (!q.isEmpty()) {
Node cur = q.poll();
for (Node nei : cur.neighbors) {
if (!clones.containsKey(nei)) {
clones.put(nei, new Node(nei.val));
q.offer(nei);
}
clones.get(cur).neighbors.add(clones.get(nei));
}
}
return clones.get(node);
}Time is expected O(n + e) — each original is offered once, each neighbor-list entry is a lookup and an add. Space is O(n) for the map and the queue, plus the n new nodes the prompt required. n is nodes; e is the total length of all neighbor lists.
Note: Always add the clone neighbor, even on a map hit. The hit is the back edge. Create-on-miss only; wire always. A map keyed by val collapses two originals with the same value into one clone; keys are node objects.
What interviewers usually poke next
TreeNode. Wrong type. There is no left/right. The adjacency list isneighbors; a missing neighbor is an empty list, notnullchildren.- DFS, same map. Recurse on originals;
putthe clone before you loop neighbors or the 2-cycle duplicates. Recursion on a long path is why BFS withArrayDequeis the default board. - Null start / isolated node.
nullreturnsnull. Emptyneighborsis a clone with an empty list — one put, zero offers of anyone else. - Key by
val. Fine only if the prompt promised unique values. Identity is the dictionary that still works when values collide. - Disconnected nodes. You clone what is reachable from the given reference. If they hand you a forest, ask which components they want.
- Iterative DFS. Same map, an
ArrayDequeused as a stack (push/pop). Still notjava.util.Stack. Still notArrayList.remove(0).
You are done with this problem when you can say, out loud, why a nested copy with no map duplicates nodes on cycles, why a linear scan per neighbor is correct and quadratic, and why you put the clone before you walk neighbors.