Log inSign up
mediumLeetCodeNot Started

Clone Graph

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value val (int) and a list (List[Node]) of its neighbors:

cpp class Node { public int val; public List<Node> neighbors; }

---

### Test Case Format For simplicity, each node's value is the same as the node's 1-based index. For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

---

### Examples

Example 1: ``text Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2: ``text Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3: ``text Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.

---

### Constraints - The number of nodes in the graph is in the range [0, 100]. - 1 <= Node.val <= 100 - Node.val is unique for each node. - There are no repeated edges and no self-loops in the graph. - The Graph is connected and all nodes can be visited starting from the given node.

Constraints:

  • 0 <= number of nodes <= 100
  • 1 <= Node.val <= 100
  • Node.val is unique for each node
  • No repeated edges and no self-loops
  • Graph is connected

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Handle cyclic reference graphs during deep copy operations.
  • Utilize a hash map to map original pointer references to cloned pointers.
  • Implement both recursive DFS and iterative Queue BFS graph cloning.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Deep copy / clone of graph or complex pointer structure with cycles
  • Copy List with Random Pointer variation on arbitrary graphs
  • Object graph serialization/deserialization

Algorithmic Decision Tree:

  • If cloning graph structure with cycles -> Maintain HashMap<OriginalNode, ClonedNode>.
  • Use DFS or BFS to traverse all reachable original nodes.
  • Wire neighbor edges using clonedNode.neighbors.append(map[originalNeighbor]).

Connected Patterns:

Copy List with Random PointerClone Binary Tree With Random NodeSerialize and Deserialize N-ary Tree

1. Iterative BFS with Queue and Hash Map

Intuition

Starting from the given root, instantiate its clone and store it in a hash map. Enqueue the original node. While the queue is non-empty, dequeue a node, iterate its neighbors, clone any unvisited neighbors, and append cloned neighbors to the current cloned node.

Algorithm

  1. If node is null, return null.
  2. Initialize queue q and push original node.
  3. Initialize hash map clonedMap: original Node* -> cloned Node*.
  4. Create clone of root: clonedMap[node] = new Node(node.val).
  5. While queue is not empty:
  6. Pop original node curr from q.
  7. For each neighbor in curr.neighbors:
  8. If neighbor not in clonedMap:
  9. clonedMap[neighbor] = new Node(neighbor.val).
  10. Push neighbor into q.
  11. clonedMap[curr].neighbors.append(clonedMap[neighbor]).
  12. Return clonedMap[node].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <queue>
5
6class Node {
7public:
8 int val;
9 std::vector<Node*> neighbors;
10 Node() : val(0) {}
11 Node(int _val) : val(_val) {}
12 Node(int _val, std::vector<Node*> _neighbors) : val(_val), neighbors(_neighbors) {}
13};
14
15class Solution {
16public:
17 Node* cloneGraph(Node* node) {
18 if (!node) return nullptr;
19
20 std::unordered_map<Node*, Node*> cloned;
21 std::queue<Node*> q;
22
23 cloned[node] = new Node(node->val);
24 q.push(node);
25
26 while (!q.empty()) {
27 Node* curr = q.front();
28 q.pop();
29
30 for (Node* neighbor : curr->neighbors) {
31 if (cloned.find(neighbor) == cloned.end()) {
32 cloned[neighbor] = new Node(neighbor->val);
33 q.push(neighbor);
34 }
35 cloned[curr]->neighbors.push_back(cloned[neighbor]);
36 }
37 }
38
39 return cloned[node];
40 }
41};
42
43int main() {
44 Node* n1 = new Node(1);
45 Node* n2 = new Node(2);
46 n1->neighbors.push_back(n2);
47 n2->neighbors.push_back(n1);
48
49 Solution sol;
50 Node* cloned = sol.cloneGraph(n1);
51 std::cout << "Original root: " << n1->val << ", Cloned root: " << cloned->val << "\n";
52 std::cout << "Cloned neighbor val: " << cloned->neighbors[0]->val << " (Expected: 2)\n";
53 return 0;
54}

Time & Space Complexity

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

2. Array-Based Direct-Index Mapping DFS

Intuition

Replacing the hash map with a fixed-size array Node* clones[101] eliminates hashing overhead and dynamic allocations, providing maximum memory locality and cache speed.

Algorithm

  1. If node is null, return null.
  2. Initialize array clones of size 101 to null.
  3. Define dfs(curr):
  4. If clones[curr.val] is not null, return clones[curr.val].
  5. Create copy = new Node(curr.val).
  6. clones[curr.val] = copy.
  7. For each neighbor in curr.neighbors:
  8. copy.neighbors.push(dfs(neighbor)).
  9. Return copy.
  10. Return dfs(node).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Node {
5public:
6 int val;
7 std::vector<Node*> neighbors;
8 Node() : val(0) {}
9 Node(int _val) : val(_val) {}
10 Node(int _val, std::vector<Node*> _neighbors) : val(_val), neighbors(_neighbors) {}
11};
12
13class Solution {
14 Node* clones[101] = {nullptr};
15
16 Node* dfs(Node* node) {
17 if (!node) return nullptr;
18 if (clones[node->val]) return clones[node->val];
19
20 Node* copy = new Node(node->val);
21 clones[node->val] = copy;
22
23 for (Node* neighbor : node->neighbors) {
24 copy->neighbors.push_back(dfs(neighbor));
25 }
26
27 return copy;
28 }
29public:
30 Node* cloneGraph(Node* node) {
31 return dfs(node);
32 }
33};
34
35int main() {
36 Node* n1 = new Node(1);
37 Node* n2 = new Node(2);
38 n1->neighbors.push_back(n2);
39 n2->neighbors.push_back(n1);
40
41 Solution sol;
42 Node* cloned = sol.cloneGraph(n1);
43 std::cout << "Array-Indexed DFS root: " << cloned->val << "\n";
44 std::cout << "Array-Indexed DFS neighbor: " << cloned->neighbors[0]->val << " (Expected: 2)\n";
45 return 0;
46}

Time & Space Complexity

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

3. Canonical Recursive DFS with Hash Map (Universal)

Intuition

The universal gold-standard interview solution. If a node has already been cloned, return its clone from the map immediately. Otherwise, create the clone, insert it into the map to guard against recursive cycles, and populate its neighbor list recursively.

Algorithm

  1. If node is null, return null.
  2. Initialize hash map cloned: Node* -> Node*.
  3. Define dfs(curr):
  4. If curr is in cloned map, return cloned[curr].
  5. Create copy = new Node(curr.val).
  6. cloned[curr] = copy (MUST insert before neighbor recursion to break cycles).
  7. For each neighbor in curr.neighbors:
  8. copy.neighbors.append(dfs(neighbor)).
  9. Return copy.
  10. Return dfs(node).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5class Node {
6public:
7 int val;
8 std::vector<Node*> neighbors;
9 Node() : val(0) {}
10 Node(int _val) : val(_val) {}
11 Node(int _val, std::vector<Node*> _neighbors) : val(_val), neighbors(_neighbors) {}
12};
13
14class Solution {
15 std::unordered_map<Node*, Node*> cloned;
16public:
17 Node* cloneGraph(Node* node) {
18 if (!node) return nullptr;
19
20 if (cloned.find(node) != cloned.end()) {
21 return cloned[node];
22 }
23
24 Node* copy = new Node(node->val);
25 cloned[node] = copy;
26
27 for (Node* neighbor : node->neighbors) {
28 copy->neighbors.push_back(cloneGraph(neighbor));
29 }
30
31 return copy;
32 }
33};
34
35int main() {
36 Node* n1 = new Node(1);
37 Node* n2 = new Node(2);
38 n1->neighbors.push_back(n2);
39 n2->neighbors.push_back(n1);
40
41 Solution sol;
42 Node* cloned = sol.cloneGraph(n1);
43 std::cout << "Canonical DFS root: " << cloned->val << "\n";
44 std::cout << "Canonical DFS neighbor: " << cloned->neighbors[0]->val << " (Expected: 2)\n";
45 return 0;
46}

Time & Space Complexity

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

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative BFS with QueueO(V + E)O(V)FIFO queue iterates over nodes while hash map tracks cloned instances.Queue memory footprint
2.Array-Based Direct-Index MappingO(V + E)O(V)Uses fixed-size array clones[101] for O(1) direct indexing without hash collisions.Value range constraint
3.Canonical Recursive DFS with Hash MapOptimalO(V + E)O(V)Pure recursive traversal with memoized original-to-clone hash map.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Inserting the clone into the map AFTER neighbor recursion, causing infinite recursion on cyclic graphs.

Pitfall 2:

Returning a shallow copy by copying neighbor pointers rather than recursively cloned nodes.

Pitfall 3:

Forgetting to check if node == nullptr, causing null pointer dereferences.

Crucial Edge Cases to Validate:

  • Empty graph (node == nullptr) — Early return nullptr immediately in O(1) time.
  • Single node with no neighbors (val = 1, neighbors = []) — Creates clone Node(1) with empty neighbors and returns it.
  • Complete graph with two nodes connected to each other (1 <-> 2) — Map stores clone of 1, recurses to 2, 2's neighbor is 1 which hits map, returning cleanly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the cycle prevention rule clearly: 'Insert the cloned node into the map before recursing on its neighbors.'
  2. Clarify whether node values are unique and bounded — if bounded (e.g. 1..100), mention the array optimization.
  3. Mention the parallel between Clone Graph and Copy List with Random Pointer.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why MUST a cloned node be stored in the hash map BEFORE recursing on its neighbors?

2.What is the difference between a shallow copy and a deep copy of a graph?

3.What should the function return when node == nullptr?

Back to DSA Sheet