Difficulty: MediumGraphs

Clone Graph

Problem in Plain English

Given one node of a connected undirected graph, build a complete independent copy with the same values and edges. Every original node maps to exactly one new node.

Problem Statement

You are given a reference to a node in a connected undirected graph and must return a deep copy (clone) of the graph.

Each node holds an integer val and a list of its neighbors. Every node is cloned exactly once: revisiting an already cloned node reuses its copy instead of creating another.

Constraints

The graph holds between 0 and 100 nodes.
1 <= Node.val <= 100
Node.val is unique across the graph.
No repeated edges and no self-loops.
The graph is connected and all values are valid.

Examples

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

Create four new nodes and four new neighbour lists. The cycle returns to the same copy 1C, and nodes 2C and 4C share the same copy 3C; matching values alone would not prove a deep copy.

Example 2

Input: adjList = [[]]
Output: [[]]

The result is a new node with value 1 and a new empty neighbour list. Returning the original isolated node would have the right printed output but violate independence.

Example 3

Input: adjList = []
Output: []

An empty graph has a null reference, so the clone is also empty.

Example 4

Input: adjList = [[2,3],[1,3],[1,2]]
Output: [[2,3],[1,3],[1,2]]

In this triangle, node 3 is reachable through node 2 and directly from node 1. Both routes reuse the same 3C, and edges back to previously visited nodes reuse their copies rather than recurse again.

Intuition

A deep copy must preserve both connections and sharing: if nodes 2 and 4 both point to node 3 in Example 1, both copied lists must point to the same new node 3C. Keep a map from each original object to exactly one copy. Record an empty copy before visiting its neighbours so the edge back to node 1 can reuse 1C even while its list is unfinished. The traversal then fills new neighbour lists without changing any original object.

Approaches

BFS Clone

Solution Details

Reveal BFS Clone: intuition, complexity, and code

Intuition

Use a queue to separate discovering a node from filling its copied neighbour list. As soon as a neighbour is discovered, allocate and map its copy, even if that copy has not been processed yet. In Example 1, node 4 can already link to 3C after node 2 discovers it. A queue gives an iterative traversal with the same asymptotic bounds as DFS.

Step-by-Step Logic

For a null input return null. Otherwise create the starting copy, map it by original object identity and enqueue the original; all traversal state belongs to this call.
While the queue is nonempty, dequeue an original and scan its neighbours in order. For each unmapped neighbour, create and record its copy and enqueue it; always append the mapped neighbour to the current copy. In Example 1, the initial map is 1 -> 1C and the queue is [1].
Dequeue 1: neighbours 2 and 4 have no copies, so create 2C and 4C, link both to 1C, and enqueue 2 and 4.
Dequeue 2: neighbour 1 already maps to 1C, so link 2C to 1C; neighbour 3 is new, so create 3C, link it, and enqueue 3.
Dequeue 4: neighbour 1 maps to 1C and neighbour 3 maps to 3C, so link 4C to both.
Dequeue 3: neighbours 2 and 4 map to 2C and 4C, so link 3C to both.
The queue is empty, so return 1C, whose adjacency mirrors [[2,4],[1,3],[2,4],[1,3]].

Why It Works

The map assigns exactly one fresh copy to each discovered original, and a node enters the queue only when that entry is created. Thus cycles cannot cause repeated processing. When an original is dequeued, its entire neighbour list is scanned in order and each corresponding mapped copy is appended to its own new list. Connectivity ensures every original is discovered, so every node value and every edge is reproduced. All appended references target fresh copies and no original list is written, establishing a deep copy.

Dry Run

BFS Clone: variable states at each step
Event	Queue after event	Copies mapped	Copied neighbour list after event
Start at 1	[1]	1:1C	1C:[]
Dequeue 1, read 2 (new)	[2]	1:1C, 2:2C	1C:[2C]
Read 4 (new)	[2,4]	add 4:4C	1C:[2C,4C]
Dequeue 2, read 1 (hit)	[4]	unchanged	2C:[1C]
Read 3 (new)	[4,3]	add 3:3C	2C:[1C,3C]
Dequeue 4, read 1 (hit)	[3]	unchanged	4C:[1C]
Read 3 (hit)	[3]	unchanged	4C:[1C,3C]
Dequeue 3, read 2 (hit)	[]	unchanged	3C:[2C]
Read 4 (hit)	[]	unchanged	3C:[2C,4C]
Return 1C	[]	four distinct copies	[[2,4],[1,3],[2,4],[1,3]]

Complexity Analysis

Time Complexity

O(V + E)

Space Complexity

O(V)

Let V be the node count and E the undirected edge count. Each node is dequeued once and all 2E neighbour entries are scanned; expected constant-time map operations give O(V + E) time. The identity map and queue use O(V) auxiliary space. The returned graph additionally allocates V nodes, V fresh lists and 2E neighbour references, so total newly allocated space including output is O(V + E). JavaScript advances a queue head instead of shifting the array, avoiding repeated element moves.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3import java.util.IdentityHashMap;4import java.util.Map;5import java.util.ArrayDeque;6import java.util.Queue;7
8class Node {9    public int val;10    public List<Node> neighbors;11    public Node(int val) {12        this.val = val;13        this.neighbors = new ArrayList<>();14    }15}16
17class Solution {18    public Node cloneGraph(Node node) {19        if (node == null) return null;20        Map<Node, Node> copies = new IdentityHashMap<>();21        Queue<Node> queue = new ArrayDeque<>();22        copies.put(node, new Node(node.val));23        queue.offer(node);24        while (!queue.isEmpty()) {25            Node curr = queue.poll();26            for (Node next : curr.neighbors) {27                if (!copies.containsKey(next)) {28                    // Record on discovery: every original is queued only once.29                    copies.put(next, new Node(next.val));30                    queue.offer(next);31                }32                // Wire only copies, including neighbours discovered through another path.33                copies.get(curr).neighbors.add(copies.get(next));34            }35        }36        return copies.get(node);37    }38}

Hints

Hint 1

Two paths can reach the same node. How will you ensure they refer to the same copied object?

Hint 2

Keep a map from original objects to copies, rather than just a visited set. A neighbour reference needs its corresponding copied object.

Hint 3

Create and memoise an empty copy before exploring its neighbours. This lets a back edge reuse the copy immediately; a null input returns null.

Edge Cases

A null reference means an empty graph and clones to null.
A single node with no neighbours clones to one isolated node.
A 100-node chain reaches the maximum recursive depth; a complete 100-node graph instead has 9900 neighbour references that must all be copied.

Common Mistakes and Interview Tips

Appending original neighbours to the copy instead of their mapped clones, producing a shallow copy.
Creating the copy after recursing into neighbours, which duplicates nodes on every cycle.
Skipping the null check and dereferencing the input before the map is even built.
Keeping a memo table on the Solution object across public calls returns stale clones and lets two results share objects. Allocate the map inside each call.
In JavaScript, repeated queue.shift() moves remaining entries and can lose the linear traversal bound. Use a monotonically increasing head index.
Interview tip: show identity and ownership, not only printed values. Two parents of node 3 must share one 3C, while no copied node or neighbour list may belong to the original.

Key Takeaway

Cloning linked structures is a memoised traversal: create the copy on first visit, record it immediately, then wire every neighbour through the map.