#133
Clone Graph
Medium DFS with old → new map
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return a deep copy of a connected undirected graph, given a reference to one node.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: deep-copy a graph.
Why this works: map each original node to its copy; register the copy before visiting neighbours so cycles stop.
Example: 1 - 2 - 3 - 4 - 1 (a square)
copy 1 → copy neighbours 2 and 4 → … each node copied once✦Hints open one at a time
Keep a HashMap from original node to its copy.
Put the copy in the map before visiting neighbours, so cycles stop there.
↗Approach
clone(node): if mapped, return the copy. Otherwise create the copy, store it, and add clone(neighbour) for every neighbour.
</>Solution (Java)
import java.util.*;
/*
* class Node { int val; List<Node> neighbors; Node(int v) { ... } } // provided by LeetCode
*/
class Solution {
private final Map<Node, Node> copies = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
Node existing = copies.get(node);
if (existing != null) return existing;
Node copy = new Node(node.val);
copies.put(node, copy); // register before recursing
for (Node nb : node.neighbors) copy.neighbors.add(cloneGraph(nb));
return copy;
}
}!Common mistake
Adding to the map after cloning neighbours — cycles then recurse forever.
Complexity
- Time: O(V + E).
- Space: O(V).
Topic: Graphs
🎬 Episodes 74–85: video coming soon