133. Clone Graph
Asked at Google, Meta, Amazon, Microsoft and 1 more
Difficulty
Medium
Time
O(V + E)
Space
O(V)
Pattern
Depth-First Search
Companies
5
Problem
You are given a reference to one node in a connected undirected graph. Every node holds an integer val and a list of neighbors. Your job is to return a deep copy of the whole graph: brand new node objects with the same values and the same connections.
The returned node must be the clone of the node you were given. The clone must not share any node object with the original graph — copying only the values is not enough, you must copy the links too.
The graph is connected, so starting from the given node you can reach every other node. Nodes have unique values, there are no self-loops and no repeated edges. The input is written as an adjacency list: the i-th inner list holds the values of the neighbors of the node with value i+1. The given node always has val = 1.
A hash map from original node to its clone is the key trick. It plays two roles: it tells you which nodes you have already copied, and it gives you the clone to attach when a neighbor points back to a node you have seen before. Without it, cycles in the graph would send you into an infinite loop.
Copy the graph, not just the values
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.
Examples
adjList = [[2,4],[1,3],[2,4],[1,3]][[2,4],[1,3],[2,4],[1,3]]adjList = [[]][[]]adjList = [][]Asked At
5 companies| 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.
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.
DFS with a map from original to clone
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
O(V + E) timeclass 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 runs in O(V + E) time and O(V) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.