Approach Summary
BFS/DFS with a hash map from original node to its clone. On each visit, create clone if not exists, then clone neighbors.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Breadth-First Search (BFS) with Hash Map | O(V + E) | O(V) | Level-by-level queue traversal allocating clone nodes and connecting duplicate edges using a hash map registry. |
| 2 Approach 2: Depth-First Search (DFS) with Hash Map (Optimal) | O(V + E) | O(V) | Recursive DFS that visits each node, clones it immediately into a hash map, and recursively populates its cloned neighbors. |
Approach 1: Breadth-First Search (BFS) with Hash Map
1. Return null if input node is null. 2. Create an empty hash map `map` from original Node pointer to cloned Node pointer. 3. Create the clone for the root node `map[node] = new Node(node.val)` and enqueue `node`. 4. While the queue is not empty, dequeue `curr`. 5. Iterate over each `neighbor` of `curr`. If `neighbor` is not in `map`, instantiate `new Node(neighbor.val)`, record in `map`, and enqueue `neighbor`. 6. Append `map[neighbor]` to `map[curr].neighbors`. 7. When queue empties, return `map[node]`.
Approach 1: Breadth-First Search (BFS) with Hash Map Implementation
Approach 1: Breadth-First Search (BFS) with Hash Map
class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> map = new HashMap<>();
Queue<Node> queue = new ArrayDeque<>();
queue.add(node);
map.put(node, new Node(node.val, new ArrayList<>()));
while (!queue.isEmpty()) {
Node curr = queue.poll();
for (Node neighbor : curr.neighbors) {
if (!map.containsKey(neighbor)) {
map.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
queue.add(neighbor);
}
map.get(curr).neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
}class Solution {
public:
Node* cloneGraph(Node* node) {
if (node == NULL) return NULL;
unordered_map<Node*, Node*> map;
queue<Node*> q;
q.push(node);
map[node] = new Node(node->val);
while (!q.empty()) {
Node* curr = q.front();
q.pop();
for (Node* neighbor : curr->neighbors) {
if (map.find(neighbor) == map.end()) {
map[neighbor] = new Node(neighbor->val);
q.push(neighbor);
}
map[curr]->neighbors.push_back(map[neighbor]);
}
}
return map[node];
}
};from collections import deque
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None
clones = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for neighbor in curr.neighbors:
if neighbor not in clones:
clones[neighbor] = Node(neighbor.val)
queue.append(neighbor)
clones[curr].neighbors.append(clones[neighbor])
return clones[node]var cloneGraph = function(node) {
if (!node) return null;
const clones = new Map();
clones.set(node, new Node(node.val));
const queue = [node];
while (queue.length > 0) {
const curr = queue.shift();
for (const neighbor of curr.neighbors) {
if (!clones.has(neighbor)) {
clones.set(neighbor, new Node(neighbor.val));
queue.push(neighbor);
}
clones.get(curr).neighbors.push(clones.get(neighbor));
}
}
return clones.get(node);
};Approach 2: Depth-First Search (DFS) with Hash Map (Optimal)
1. Maintain a hash map `clones` mapping each original node to its clone. 2. In `dfs(node)`: - If `node == null`, return null. - If `node` already exists in `clones`, return `clones[node]`. - Instantiate `clone = new Node(node.val)` and cache `clones[node] = clone` immediately to handle cycles. - For each neighbor in `node.neighbors`, append `dfs(neighbor)` to `clone.neighbors`. - Return `clone`. 3. Avoids queue overhead and provides concise implementation.
Approach 2: Depth-First Search (DFS) with Hash Map (Optimal) Implementation
Approach 2: Depth-First Search (DFS) with Hash Map (Optimal)
class Solution {
private Map<Node, Node> clones = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
if (clones.containsKey(node)) return clones.get(node);
Node clone = new Node(node.val, new ArrayList<>());
clones.put(node, clone);
for (Node neighbor : node.neighbors) {
clone.neighbors.add(cloneGraph(neighbor));
}
return clone;
}
}class Solution {
unordered_map<Node*, Node*> clones;
public:
Node* cloneGraph(Node* node) {
if (node == NULL) return NULL;
if (clones.find(node) != clones.end()) return clones[node];
Node* clone = new Node(node->val);
clones[node] = clone;
for (Node* neighbor : node->neighbors) {
clone->neighbors.push_back(cloneGraph(neighbor));
}
return clone;
}
};class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
clones = {}
def dfs(curr):
if not curr:
return None
if curr in clones:
return clones[curr]
clone = Node(curr.val)
clones[curr] = clone
for neighbor in curr.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)var cloneGraph = function(node) {
const clones = new Map();
function dfs(curr) {
if (!curr) return null;
if (clones.has(curr)) return clones.get(curr);
const clone = new Node(curr.val);
clones.set(curr, clone);
for (const neighbor of curr.neighbors) {
clone.neighbors.push(dfs(neighbor));
}
return clone;
}
return dfs(node);
};Edge Cases to Watch
- Null/empty graph — node is null, return null immediately
- Single node with no neighbors (val = 1, neighbors = []) — return clone with empty list
- Self-loops (node having an edge to itself) — the map ensures the node is not re-cloned indefinitely
- Cycles and dense graphs — hash map prevents infinite recursion or re-enqueuing
Master the Graphs Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Graphs pattern.
How to Recognize This Pattern
- Deep copy of graph
- Map from original to clone
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V)