#133 Clone Graph
the problem
In plain words
Given a reference to a node in a connected undirected graph, return a deep copy. Each node has val and a list of neighbors.
in adjList = [[2,4],[1,3],[2,4],[1,3]]
out [[2,4],[1,3],[2,4],[1,3]]
A square 1-2-3-4. The copy must use brand-new nodes.
in adjList = [[]]
out [[]]
in adjList = []
out []
- 0 ≤ number of nodes ≤ 100
- Node values are unique, 1..100
- No repeated edges, no self-loops; the graph is connected
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGraph DFS / BFS traversalHash lookup (seen before?)
A HashMap from original to clone is both the visited set and the way to reuse clones. Register the clone before visiting neighbours, or cycles recurse forever.
solutions
From brute force to optimal
clone(node): if already cloned, return it; else create it, store it, then clone each neighbour.
- Map<Node, Node> copies.
- If node in copies, return copies.get(node).
- Create copy, put it in the map, then add clone(neighbour) for each neighbour.
Each node is cloned once; each edge is wired once per direction.
The map holds V entries; recursion depth ≤ V.
class Solution { private final Map<Node, Node> copies = new HashMap<>(); // original → its clone public Node cloneGraph(Node node) { if (node == null) return null; if (copies.containsKey(node)) return copies.get(node); // already cloned: reuse (stops cycles) Node copy = new Node(node.val); copies.put(node, copy); // register BEFORE recursing into neighbours for (Node nb : node.neighbors) { copy.neighbors.add(cloneGraph(nb)); // clone (or reuse) nb, then wire the edge } return copy; }}Dry run
Clone nodes when first discovered; wire edges while polling.
- Clone the start, enqueue it.
- Poll cur; for each neighbour, clone + enqueue it if new, then add its clone to cur's clone.
Each node polled once; each adjacency entry handled once.
Map plus queue.
class Solution { public Node cloneGraph(Node node) { if (node == null) return null; Map<Node, Node> copies = new HashMap<>(); copies.put(node, new Node(node.val)); Deque<Node> queue = new ArrayDeque<>(); queue.offer(node); while (!queue.isEmpty()) { Node cur = queue.poll(); for (Node nb : cur.neighbors) { if (!copies.containsKey(nb)) { // first time we see nb: clone it and explore it later copies.put(nb, new Node(nb.val)); queue.offer(nb); } copies.get(cur).neighbors.add(copies.get(nb)); // wire the cloned edge } } return copies.get(node); }}in the room
How to say it in the interview
talk track
- Say: "The map plays two roles: visited set and lookup from original to copy."
- Handle
node == nullfirst.
traps
- Putting the clone in the map after recursing into neighbours → infinite recursion on any cycle.
- Returning original neighbours inside the copy (a shallow copy).
what they ask next
Follow-ups
Copy List with Random Pointer (LC 138)?
Same trick: a map from old node to new node, then wire next and random through the map.
before you submit
Edge cases to test
- Empty graph (node == null) → return null.
- A single node with no neighbours → one new node, empty list.
- Two nodes pointing at each other: without registering the copy first, the recursion never ends.
practise next
Similar problems
- #138Copy List with Random PointerMediumin Linked Lists
- #200Number of IslandsMediumin Graphs