Given a reference to a vertex of a connected undirected graph, where each vertex has a value and a list of neighbors, return a deep copy of the graph.
Before you code
A graph has cycles, so a naive recursive copy would loop forever. The map from original vertex to copy doubles as the visited set.
Hints
- Keep
copies = {original: clone}. - Traverse with BFS or DFS. When you meet a neighbor with no copy yet, create it and schedule it for processing.
- Append the neighbor's copy to the current clone's neighbor list.
Production & complexity notes
When solving Clone graph on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Representing graphs to reinforce the underlying pattern.
What it practices
Walking adjacency lists with a visited map, from Representing graphs.