Clone Graph
Clone Graph is a medium graphs problem solved with the bfs / dfs basics pattern.
The best approach, optimal (bfs with a map from original to copy), runs in O(V + E) time and O(V) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs with a map from original to copy up.
Problem
You are given a reference to one node of a connected, undirected graph. Each node stores an integer val and a list neighbors of the nodes it is connected to. Return a deep copy of the whole graph: a brand-new set of nodes with the same values and the same connections, where no node of the copy is a node of the original.
In the examples the graph is written as an adjacency list: entry i (1-based) lists the values of node i’s neighbors. The node you receive is always the one with value 1, and node i has value i. If the graph is empty, the given node is null and you return null.
Examples
Example 1
- Input
adjList = [[2, 3], [1, 3], [1, 2]]- Output
[[2, 3], [1, 3], [1, 2]]- Why
- A triangle: every node touches the other two. The copy has three new nodes wired the same way.
Example 2
- Input
adjList = [[2], [1, 3], [2, 4], [3]]- Output
[[2], [1, 3], [2, 4], [3]]- Why
- A path 1 - 2 - 3 - 4. Starting from node 1, every node is reached and copied.
Example 3
- Input
adjList = []- Output
[]- Why
- There is no graph, so the answer is null.
Constraints
0 <= number of nodes <= 1001 <= Node.val <= 100, and every value is unique (node i has value i).- The graph is undirected and connected, with no self-loops and no repeated edges.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| DFS with a map from original to copy | O(V + E) | O(V) |
| Optimal (BFS with a map from original to copy) | O(V + E) | O(V) |
1DFS with a map from original to copy
O(V + E)Each node is copied once and each edge is followed twice (once from each end).O(V)The map holds V entries and the recursion can go V levels deep.Recursively copy the graph. Before copying a node, look it up in a map; if it is already there, return the existing copy, which also stops the recursion on cycles.
- If the node is null, return null.
- If the map already holds a copy of this node, return it.
- Create the copy, store it in the map before visiting neighbors.
- For each neighbor, append clone(neighbor) to the copy's neighbor list.
class Solution {
private final Map<Node, Node> copies = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
Node seen = copies.get(node);
if (seen != null) return seen;
Node copy = new Node(node.val);
copies.put(node, copy);
for (Node nb : node.neighbors) {
copy.neighbors.add(cloneGraph(nb));
}
return copy;
}
}class Solution:
def __init__(self):
self.copies = {}
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if node is None:
return None
if node in self.copies:
return self.copies[node]
copy = Node(node.val)
self.copies[node] = copy
for nb in node.neighbors:
copy.neighbors.append(self.cloneGraph(nb))
return copyclass Solution {
unordered_map<Node*, Node*> copies;
public:
Node* cloneGraph(Node* node) {
if (node == nullptr) return nullptr;
auto it = copies.find(node);
if (it != copies.end()) return it->second;
Node* copy = new Node(node->val);
copies[node] = copy;
for (Node* nb : node->neighbors) {
copy->neighbors.push_back(cloneGraph(nb));
}
return copy;
}
};function cloneGraph(node, copies = new Map()) {
if (node === null) return null;
if (copies.has(node)) return copies.get(node);
const copy = new Node(node.val);
copies.set(node, copy);
for (const nb of node.neighbors) {
copy.neighbors.push(cloneGraph(nb, copies));
}
return copy;
}2Optimal (BFS with a map from original to copy)
O(V + E)Every node is enqueued once and every adjacency entry is scanned once.O(V)The map and the queue each hold at most V nodes.Walk the graph level by level with a queue. The first time a node is seen, create its copy and enqueue it. When a node is dequeued, link its copy to the copies of all its neighbors. No recursion, so a long path cannot overflow the call stack.
- If the node is null, return null.
- Copy the start node, put it in the map and in the queue.
- Pop a node; for every neighbor: if it has no copy yet, create one, store it and enqueue the neighbor.
- Append the neighbor's copy to the popped node's copy.
- Return the copy of the start node.
class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> copies = new HashMap<>();
copies.put(node, new Node(node.val));
Deque<Node> queue = new ArrayDeque<>();
queue.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (Node nb : cur.neighbors) {
if (!copies.containsKey(nb)) {
copies.put(nb, new Node(nb.val));
queue.add(nb);
}
copies.get(cur).neighbors.add(copies.get(nb));
}
}
return copies.get(node);
}
}class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if node is None:
return None
copies = {node: Node(node.val)}
queue = deque([node])
while queue:
cur = queue.popleft()
for nb in cur.neighbors:
if nb not in copies:
copies[nb] = Node(nb.val)
queue.append(nb)
copies[cur].neighbors.append(copies[nb])
return copies[node]class Solution {
public:
Node* cloneGraph(Node* node) {
if (node == nullptr) return nullptr;
unordered_map<Node*, Node*> copies;
copies[node] = new Node(node->val);
queue<Node*> q;
q.push(node);
while (!q.empty()) {
Node* cur = q.front();
q.pop();
for (Node* nb : cur->neighbors) {
if (!copies.count(nb)) {
copies[nb] = new Node(nb->val);
q.push(nb);
}
copies[cur]->neighbors.push_back(copies[nb]);
}
}
return copies[node];
}
};function cloneGraph(node) {
if (node === null) return null;
const copies = new Map();
copies.set(node, new Node(node.val));
const queue = [node];
let head = 0;
while (head < queue.length) {
const cur = queue[head++];
for (const nb of cur.neighbors) {
if (!copies.has(nb)) {
copies.set(nb, new Node(nb.val));
queue.push(nb);
}
copies.get(cur).neighbors.push(copies.get(nb));
}
}
return copies.get(node);
}Edge cases to test
- An empty graph (the given node is null)
- A single node with no neighbors
- Cycles: without remembering visited nodes the copy loops forever
Hints
Hint 1
Each original node must map to exactly one copy. What structure lets you ask "have I already copied this node?"
Hint 2
Keep a map from original node to its copy. Create the copy the first time you see a node, then fill its neighbor list with the copies of its neighbors.
Hint 3
Either DFS (recursion) or BFS (a queue) can drive the walk; the map doubles as the visited set.
FAQ
What is the best time complexity for Clone Graph?
Optimal (BFS with a map from original to copy) runs in O(V + E) time and O(V) extra space. Every node is enqueued once and every adjacency entry is scanned once.
Which pattern does Clone Graph use?
It is a graphs problem that uses the bfs / dfs basics pattern. Other problems with the same pattern: BFS - Normal + Level by Level, DFS - Recursive + Iterative, All Paths From Source to Target.
Is there a brute force solution for Clone Graph?
Yes. DFS with a map from original to copy takes O(V + E) time and O(V) space. Recursively copy the graph.
Which edge cases should I test for Clone Graph?
An empty graph (the given node is null); A single node with no neighbors; Cycles: without remembering visited nodes the copy loops forever.