Clone Graph
Problem Statement
Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains an integer value and a list of its neighbours.
The clone must be entirely independent of the original: cloning a node means creating a brand-new node with the same value and cloned neighbour references — no node from the original graph may appear in the copy.
Input
A reference to one Node of the graph (or null for an empty graph). On LeetCode the graph is given as an adjacency list, but your function receives a single starting Node.
Output
A reference to the corresponding node in the fully cloned graph.
Constraints
- •
The number of nodes is in the range [0, 100]. - •
1 <= Node.val <= 100, and Node.val is unique for each node. - •
There are no repeated edges and no self-loops. - •
The graph is connected, so all nodes are reachable from the given node.
Examples
Example 1
adjList = [[2,4],[1,3],[2,4],[1,3]]
[[2,4],[1,3],[2,4],[1,3]]Example 2
adjList = [[]]
[[]]Example 3
adjList = []
[]Learning Objectives
- Traverse a general (non-grid) graph given only a starting node reference.
- Use a hash map from original node to its clone to handle cycles and shared neighbours.
- See why the visited map does double duty: it prevents infinite loops AND wires up shared references correctly.
Intuition
You cannot just recurse into neighbours blindly — the graph has cycles, so a naive DFS would clone the same node again and again forever. The fix is a map from each original node to its single clone. Before cloning a node, check the map: if a clone already exists, return it; otherwise create the clone, record it in the map immediately (before touching neighbours), then clone the neighbours.
Recording the clone before recursing is the crucial ordering. It means that when the traversal eventually loops back to a node it is midway through cloning, it finds the already-created clone in the map and links to it instead of spiralling into infinite recursion. The map is simultaneously your visited-set and your original→copy lookup table.
Common mistakes
- ×Putting the node into the map *after* cloning its neighbours — with a cycle this recurses forever.
- ×Returning null for a single isolated node instead of a cloned node (only the empty-graph case is null).
- ×Sharing neighbour lists between original and clone, which leaks references from the original graph into the copy.
- ×Using node value as the map key when values are not guaranteed unique — key by the node object itself unless uniqueness is stated.
Algorithm Explanation
- If the start node is null, return null.
- Keep a map originalToClone.
- To clone a node: if it is already in the map, return its clone. Otherwise create a new node with the same value, store it in the map, then recurse to clone each neighbour and append the clones to the new node's neighbour list.
- Because every node is inserted into the map before its neighbours are processed, each node is cloned exactly once even in the presence of cycles.
Solutions
Solution 1: DFS with a clone map
The cleanest formulation and easy to reason about. Prefer it unless recursion depth is a concern for very large graphs.
Recursively clone the start node, memoising each clone in a HashMap keyed by the original node so cycles resolve to the existing copy.
Step-by-step
- cloneGraph(node) returns null for null and the memoised clone if present.
- Otherwise it creates the copy, stores original→copy in the map before recursing (this breaks cycles), then clones each neighbour.
- The map ensures every node and edge is copied exactly once.
O(V + E)
O(V)
Every node and edge is processed once; the map and recursion stack hold O(V).
Java implementation
Solution 2: BFS with a clone map
Preferred when you want to avoid recursion on large graphs. Creates all clones first, then wires up neighbours level by level.
Clone the start node, then BFS: for each dequeued original, ensure each neighbour has a clone (create + enqueue if new) and attach the neighbour's clone to the current node's clone.
Step-by-step
- Seed the map with start→clone(start) and enqueue start.
- Pop an original node; for every neighbour, create its clone and enqueue it the first time you see it.
- Always append the neighbour's clone to the current clone's neighbour list.
- The map guarantees one clone per node; the queue guarantees each node's edges are wired once.
O(V + E)
O(V)
Queue and map are both bounded by the number of nodes.
Java implementation
Dry Run
Sample input
Graph: 1 — 2 and 1 — 3 and 2 — 3 (a triangle). DFS starting at node 1.
| Step | Cloning | Map (orig → clone) | Action |
|---|---|---|---|
| 1 | node 1 | {1→1'} | Create 1', recurse into 2 |
| 2 | node 2 | {1→1', 2→2'} | Create 2', recurse into 1 |
| 3 | node 1 | hit | 1' already in map, link 2'→1' |
| 4 | node 3 | {...,3→3'} | Create 3' from node 2, recurse into 1,2 |
| 5 | nodes 1,2 | hit, hit | Both cloned; link 3'→1', 3'→2' |
| 6 | back to node 1 | hit | Link 1'→2', 1'→3' |
Every node is created exactly once. When the recursion revisits an already-cloned node it reads the clone from the map and links to it, so the triangle's cycle resolves without infinite recursion.
Interview Tips
Lead with the cycle problem and the map-before-recurse insight — that is the entire point of the question. Be explicit that the map key should be the node object (not its value) unless the interviewer guarantees unique values. Expect a follow-up on how this generalises to serialising/deserialising a graph, or copying a linked list with random pointers (same memoisation idea).
Likely follow-ups
- Copy List with Random Pointer — the same original→copy map technique on a linked list.
- Serialize and deserialize the graph to a string and back.
- What changes if the graph is directed or disconnected? (You would need an outer loop over all nodes.)
Similar Problems
Key Takeaways
- A HashMap from original node to clone is the standard tool for deep-copying graphs.
- Insert into the map before recursing into neighbours to break cycles.
- The clone map doubles as the visited set for a general graph.