Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node holds an integer val and a list of its neighbors.
The graph is given in adjacency-list form: adjList[i] lists the neighbors of the node with value i + 1 (node values are the contiguous range 1..N, so the array is 0-indexed but values are 1-indexed). For example [[2,4],[1,3],[2,4],[1,3]] is a 4-node square: node 1 borders 2 and 4, node 2 borders 1 and 3, and so on. Your function receives the node with value 1.
Return the clone as the equivalent adjacency list.
Grading note. The tests serialize your returned graph and compare its structure to the expected adjacency list — they verify you rebuilt the right shape, but they cannot detect a solution that returns the original graph instead of a fresh copy (serialization erases object identity). Still write a genuine deep copy: allocate new nodes and wire new neighbor links.
Example
A 4-cycle. The clone has the same four nodes and the same adjacency, rebuilt as new objects.
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, and all nodes can be reached from the given node.
Intuition
We must return a deep copy of a connected undirected graph — every node and every edge rebuilt as fresh objects. The trap a naïve attempt falls into: walk the graph and, for each node, immediately recurse into its neighbours. With cycles (and an undirected graph is full of them — every edge is a 2-cycle), that recursion never terminates and clones the same node endlessly.
function cloneGraph(node) {
if (!node) return null;
const copy = new GraphNode(node.val);
// BUG: a neighbour points back at `node`, so this recurses into `node`
// again, clones it again, and never stops.
for (const neighbor of node.neighbors) {
copy.neighbors.push(cloneGraph(neighbor));
}
return copy;
}The fix is one piece of state: remember the clone we've already made for each original node. Can we do better than looping forever? Yes — with a Map from original node → its clone.
The key observation: that map does double duty. It dedupes — a node reached from several neighbours is cloned once — and it breaks cycles — when a back-edge revisits a node, the map already holds its (possibly in-progress) clone, so we return that instead of recursing. The discipline is record the clone in the map before recursing into its neighbours, so a back-edge finds it. This is a standard DFS with a visited map.
A graph isn't a sequence or a grid, so there's no faithful lane or board animation here — laying the four nodes of the example on a circle, the clone proceeds like this. Take the square 1—2—3—4—1 (node 1 borders 2 and 4, and so on around the ring):
- Grading is structure-only. The tests serialize the returned graph back to an adjacency list and compare shape — they confirm you rebuilt the right nodes and edges, but serialization erases object identity, so they cannot catch a solution that returns the original graph unmodified. Still write a genuine deep copy (allocate new
GraphNodes, wire new links); the structural check is necessary, not sufficient. - Record before you recurse. Inserting the clone into the map after recursing into neighbours reopens the infinite loop — the back-edge runs before the map entry exists.
Optimization
DFS with a visited map
Walk the graph from the given node, cloning as you go. A Map from each original node to its clone does double duty: it remembers the copies you've made (so a node shared by several neighbors is cloned once) and it breaks cycles (revisiting a node returns its existing clone instead of recursing forever).
For each original node, make its clone, record it in the map before recursing into neighbors (so a back-edge finds the in-progress clone), then attach a cloned neighbor for each original neighbor.
O(V + E) time — every node and edge is visited once — and O(V) space for the map plus recursion.
function cloneGraph(node) {
// Empty graph: nothing to clone.
if (!node) return null;
// Map each original node to its clone — dedupes shared nodes and breaks cycles.
const clones = new Map();
const dfs = (curr) => {
// Already cloned (or mid-clone): return the existing copy, closing any cycle.
if (clones.has(curr)) return clones.get(curr);
// Clone this node and record it BEFORE recursing, so a back-edge sees it.
const copy = new GraphNode(curr.val);
clones.set(curr, copy);
// Clone each neighbor and wire it into the copy.
for (const neighbor of curr.neighbors) copy.neighbors.push(dfs(neighbor));
return copy;
};
return dfs(node);
}Complexity analysis
Time complexity: O(V + E). Here's why:
- The DFS visits each node once (the map guard returns immediately on a repeat).
- For each node it walks its neighbour list, and across all nodes that's every edge counted twice (once from each endpoint).
So the work is proportional to nodes plus edges — O(V + E).
Space complexity: O(V). Here's why:
- The
Mapfrom original node to clone holds one entry per node,O(V). - The recursion stack is at most
O(V)deep on a path-shaped graph.
The clone itself is the required output (not counted as extra), so the auxiliary space is O(V).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| node = [] | [] | Empty graph — the function returns null, serialized as []. |
| node = | [[]] | A single node with no neighbours clones to the same shape. |
| node = 24 13 24 13 | [[2,4],[1,3],[2,4],[1,3]] | A 4-cycle (the example square) — structure preserved across the clone. |
| node = [[2],[1,3,4],[2],[2]] | [[2],[1,3,4],[2],[2]] | A star centred on node 2 — one hub, three leaves; the hub is cloned once and shared. |
| node = 26 13 24 35 46 15 | [[2,6],[1,3],[2,4],[3,5],[4,6],[1,5]] | A 6-cycle — a longer ring whose closing back-edge must reuse the existing clone. |
Try it yourself
Write your solution against the real judge before checking the reference.