Clone Graph
Maintained by Vikas D, software engineer
You receive a graph encoded as an adjacency list. The list is an array where the entry at index i holds the neighbors of node i, and every value is a node index in the same array.
Your job is to produce a fresh adjacency list that describes the identical graph. Node i in the copy must point to the same set of neighbors as node i in the input, and the neighbors inside each list must appear in the same order they were given.
The graph is undirected, so if node a lists b as a neighbor then b lists a too. It is connected when it has at least one node, which means a traversal from any starting node can reach every other node. There are no self-loops and no duplicate edges.
An empty input (no nodes) should give back an empty list, and a single node with no edges should give back a list holding one empty neighbor list.
Examples
A four-node cycle 0-1-2-3-0. The copy repeats each node's neighbor list in the original order, so the result matches the input value for value.
Two nodes joined by a single edge. Node 0 points to node 1 and node 1 points back to node 0, and the copy preserves both.
One node with no edges. The copy still has one entry, an empty neighbor list.
Constraints
- The number of nodes is in the range 0 to 100.
- Node values are 0-indexed and act as positions in the adjacency list.
- No self-loops and no repeated edges.
- If the graph has at least one node it is connected.
- Neighbor order within each list must be preserved in the output.
Visible test cases
- cloneGraph([[1,3],[0,2],[1,3],[0,2]]) == [[1,3],[0,2],[1,3],[0,2]]
- cloneGraph([[1],[0]]) == [[1],[0]]
- cloneGraph([[]]) == [[]]
- cloneGraph([[1,2],[0,2],[0,1]]) == [[1,2],[0,2],[0,1]]
- cloneGraph([[1,2,3],[0],[0],[0]]) == [[1,2,3],[0],[0],[0]]
- cloneGraph([]) == []
Hints
Hint 1
The output has the same shape as the input: one neighbor list per node, with neighbors in the same order. What is the simplest way to reproduce that shape?
Hint 2
If you walk the graph from a starting node, a visited marker per node stops you from looping forever on cycles like 0-1-2-3-0.
Hint 3
You can copy every node's neighbor list as you reach it during a traversal, or you can just rebuild each list directly by index since the values are plain integers.
Approaches
BFS traversal copy
Time O(V + E) · Space O(V)Treat the input as a real graph: start at node 0, walk outward breadth first, and record each node's neighbors into a fresh list as you visit it. A visited array keeps the walk from cycling.
- Return an empty list when there are no nodes.
- Create an output array of n empty lists and a visited array of length n.
- Mark node 0 visited and push it onto a queue.
- Pop a node, copy each of its neighbors into the output list for that node, and enqueue any neighbor not yet visited.
- Repeat until the queue drains, then return the output.
Direct index rebuild
Time O(V + E) · Space O(V + E)Because each node is identified by its index and neighbors are plain integers, an independent copy is just a new array holding a fresh copy of every neighbor list. No graph walk is needed.
- For each index i in the input, build a new list containing the same neighbor values in the same order.
- Collect those new lists into a new outer array.
- Return the new array, which shares no references with the input.
Common mistakes
- Returning the input itself or pushing the original neighbor arrays into the result. That is an alias, not a clone, so a later edit to the copy would change the original.
- Forgetting the visited check during a traversal. Cycles such as 0-1-2-3-0 then loop forever.
- Reordering neighbors, for example by sorting them. The output must keep each node's neighbor order exactly as given.
- Mishandling the empty graph: an input of [] must return [], while [[]] (one isolated node) must return [[]].
Follow-up variations
- Suppose the graph is given as real node objects with references instead of integer indices. How would you map each original node to its clone?
- What changes if the graph is directed rather than undirected?
- How would you clone a graph that may be disconnected, so a single BFS from node 0 cannot reach everything?
- Can you do the clone with a recursive depth-first traversal, and what is the risk on a long path?