Clone Graph
Asked at Google, Meta, Amazon, Microsoft, Uber
Problem
Given a reference of a node in a connected undirected graph, return a deep copy of the graph. Each node contains a value and a list of its neighbors.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Use a hash map to map original nodes to their clones. This prevents infinite loops and duplicate work.
DFS: for each node, if not yet cloned, create a clone, add to map, then recursively clone all neighbors. Attach cloned neighbors to the cloned node.
BFS alternative: same idea but use a queue. Enqueue the original node, clone it, then enqueue unvisited neighbors.
The hash map serves as both the visited set and the mapping. If a node is already in the map, return its clone immediately.
Visual walkthrough for graph: 1—2, 1—4, 2—3, 3—4:
Clone node 1 → map={1:clone1}. neighbors: [2, 4]
Clone node 2 → map={1:clone1, 2:clone2}. neighbors: [1, 3]
Node 1 already in map → return clone1. Clone node 3 → map={..., 3:clone3}. neighbors: [2, 4]
Node 2 already in map → return clone2. Clone node 4 → map={..., 4:clone4}. neighbors: [1, 3]
Both 1 and 3 in map → return clone1, clone3.
Result: clone1—clone2, clone1—clone4, clone2—clone3, clone3—clone4.
Edge cases: single node with no neighbors, self-loop, disconnected components (not possible per problem statement).
Optimal Approach
Step 1: If node is null, return null.
Step 2: Create hash mapcloned = {original: clone}.
Step 3: DFS function: if node in cloned, return cloned[node]. Create new node, add to map. For each neighbor, recursively clone and attach.
Step 4: Return cloned[node].
Time: O(V + E) — visit every node and edge once. Space: O(V) — hash map and recursion stack.
What Trips People Up in Real Interviews
Not using a visited map. Without it, you'll get infinite loops on cyclic graphs.
Confusing "deep copy" with "shallow copy." A deep copy means the cloned graph has no references to the original graph's nodes.
Not handling null input. If the reference node is null, return null.
Forgetting to clone all neighbors. After cloning a node, recursively clone all its neighbors and attach them.
Using BFS instead of DFS. Both work, but DFS is more natural for recursive graph cloning and uses less explicit state. BFS requires a queue and more bookkeeping.
Solution Code
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors or []
def cloneGraph(node):
if not node:
return None
cloned = {}
def dfs(n):
if n in cloned:
return cloned[n]
copy = Node(n.val)
cloned[n] = copy
for neighbor in n.neighbors:
copy.neighbors.append(dfs(neighbor))
return copy
return dfs(node)Frequently Asked Questions
What is the Clone Graph problem?
Given a reference of a node in a connected undirected graph, return a deep copy of the graph. Each node contains a value and a list of its neighbors.
How do you solve Clone Graph?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Clone Graph?
Clone Graph is asked at Google, Meta, Amazon, Microsoft, Uber. It is a medium difficulty problem.
What are common mistakes on Clone Graph?
- Not using a visited map. Without it, you'll get infinite loops on cyclic graphs.
- Confusing "deep copy" with "shallow copy." A deep copy means the cloned graph has no references to the original graph's nodes.
- Not handling `null` input. If the reference node is `null`, return `null`.
- Forgetting to clone all neighbors. After cloning a node, recursively clone all its neighbors and attach them.
- Using BFS instead of DFS. Both work, but DFS is more natural for recursive graph cloning and uses less explicit state. BFS requires a queue and more bookkeeping.