Clone Graph

Difficulty: Medium

Problem

You receive a reference to a single node in a connected undirected graph. Every node stores a value and a list of references to its neighbouring node objects (not indices). Build and return a DEEP COPY: all new node objects, connected in exactly the same way as the originals, with nothing shared with the source graph. For input and output, the graph is serialized as an adjacency list in which position i holds the neighbour values of the node numbered i+1.

Example

Input: adjList = [[2,3],[1],[1]]
Output: [[2,3],[1],[1]]
Explanation: Node 1 is joined to nodes 2 and 3, forming a small star. The copy serializes to the same adjacency list, but each of its three nodes is a fresh object, so changing the copy leaves the original untouched.

Brute-force approach

No brute-force phase here, without the old→new map, every attempt breaks on shared neighbors and cycles. The map IS the algorithm.

Optimal approach

Key insight: One map answers both dangerous questions: 'did I already clone this node?' and 'where is its clone?'. Create each clone exactly once; wire every edge to clones only.

BFS over the ORIGINAL graph while an old→new map builds the copy on the side: clone each node the first time it's seen, and recreate every edge between clones only.

Steps

Null guard: an empty graph clones to null
Seed the map with the entry node's clone; start BFS from the ORIGINAL node
Pop an original; for each neighbor not yet in the map, create its clone and enqueue the original
Always wire clones[cur] → clones[nb], every edge, copies only
Return clones[node], the entry point of the new graph

Time complexity: O(V + E) · Space complexity: O(V)

Pseudocode

function cloneGraph(node):
    if node is null:
        return null
    
    clones = { node: ____ }          // seed: the entry node's copy
    queue = [node]
    
    while queue not empty:
        cur = queue.pop_front()
        for nb in cur.neighbors:
            if nb not in ____:
                clones[nb] = ____
                queue.push(nb)
            clones[cur].neighbors.append(____)
    
    return clones[node]

Hints

The seed: before BFS even starts, the entry node needs its brand-new copy in the ledger, a fresh Node carrying node.val
The membership check is the map's visited-set job: which structure do you ask whether nb has been cloned already?
First sight of nb → mint its one-and-only clone: a new Node with nb's value (and remember to enqueue the ORIGINAL)
The wire connects copy to copy: look up the neighbor's clone in the map, never append nb itself

Complexity questions

What is the time complexity of BFS-with-a-map cloning?

O(V + E): each node is cloned once, each edge wired twice (once per endpoint). The map guarantees every node is created and enqueued exactly once, O(V). The neighbor loop touches each undirected edge from both of its endpoints, O(E). Merely reading the graph already costs O(V + E), so the cloning is asymptotically free.

What auxiliary space does the algorithm use?

O(V): the map holds one entry per node and the queue never exceeds V. The map stores exactly one entry per node and the queue holds at most V originals. The clone graph itself occupies O(V + E), but it isn't 'extra'. It's the answer we were asked to build. Auxiliary space is the map plus the queue: O(V).

Each undirected edge gets wired TWICE during the run. Why, and why is that correct?

Each endpoint appends the other during its own turn (original 1 wires 1' → 2', original 2 wires 2' → 1') exactly mirroring the originals. In the original, an undirected edge already lives as TWO list entries: 2 sits in node 1's neighbors and 1 sits in node 2's. The wire line runs once per entry, so the clone receives both directions: a perfect mirror of the originals, not a duplicate.

In the recursive (DFS) version of this solution, what replaces the queue?

The call stack: on first sight recurse dfs(nb); otherwise just return clones[nb] from the map. DFS keeps the identical map; only the engine changes. First sight of a node → create its clone, then recurse to fill in its neighbors. Already seen → the map instantly hands back the finished (or still-in-progress) clone, and that in-progress case is exactly what survives cycles.

Check your understanding of Clone Graph

In this problem, what exactly makes the returned copy a DEEP copy?

Brand-new node objects wired in the same shape, modifying the copy never touches the original. Deep means new objects all the way down: a fresh Node for every original, connected exactly like the originals. Reusing the old objects is a shallow copy, and keeping only values throws the wiring away. The defining test: mutate the copy, and the original must not flinch.

In the square 1-2-3-4-1, node 1 is a neighbor of BOTH node 2 and node 4. What goes wrong with the naive recursion 'clone me, then clone each of my neighbors'?

Node 1 gets cloned again from every path that reaches it. The copy's shape breaks, and the cycle makes the recursion run forever. Cloning node 2 dutifully re-clones its neighbor node 1, which re-clones node 2... A node reachable two ways gets two copies, so the shape breaks, and in a cycle the calls never stop at all. The fix is memory: remember which originals have already been cloned.

What SINGLE data structure fixes both problems at once?

A map from original → clone: a visited set and a phonebook in one. A bare visited set can answer 'yes, I already cloned node 1', but then can't hand you 1' when an edge needs wiring! The map does both jobs: the key being present means 'already cloned' (visited set), and the value IS the clone (phonebook).

You're wiring the clone of node 1, whose original neighbors are nodes 2 and 4. Which objects go into 1'.neighbors?

clones[2] and clones[4]: the CLONES of the neighbors, looked up in the map. Copies connect only to copies. Append an original and your 'clone' now reaches straight into the real graph: one careless link merges the two. And minting fresh nodes on the spot recreates the duplicate-clone bug the map was built to prevent.

Which traversal must drive the copying, BFS or DFS?

Either: any traversal that visits every node once works; the map does the correctness work. The traversal is just the delivery truck: its only duty is to reach every node so every clone gets made and wired. Wide (BFS) or deep (DFS) changes nothing. The old→new map is what guarantees one clone per node and copy-only wiring.