Clone Graph
On this page
Problem statement
Given a reference to one node of a connected undirected graph, return a deep copy of the whole graph. Each node has a value and a list of neighbours. The copy must use only new nodes, with the same values and the same connections.
It looks like a simple traversal, but cycles make a naive recursive copy loop forever. The fix, a map from each original node to its copy, is the same trick used for Copy List with Random Pointer. Original problem: LeetCode 133.
Example

Input: adjacency = [[2,4], [1,3], [2,4], [1,3]] # node 1's neighbours are 2 and 4, …
Output: the same adjacency, built from new nodes
Input: null
Output: null
Constraints (assumed)
- 0 ≤ nodes ≤ 100; values are unique, from 1 to n.
- The graph is connected and undirected; no self-loops or repeated edges.
What this question tests
- Graph traversal with a visited structure on a graph with cycles.
- Using a hash map from old object to new object to rebuild references.
- Clear reasoning about deep vs shallow copies.
Questions to ask first
- Is the graph connected? (Here: yes, so one start node reaches everything.)
- Are values unique? If yes you could key by value; keying by node works either way.
- Directed or undirected? (Undirected; each edge appears in both neighbour lists.)
- Can the input be empty? (Yes, return null.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.