133. Clone Graph
mediumGiven a reference to a node in a connected undirected graph, return a deep copy of the graph. Tests whether you can traverse a graph and build a parallel structure in one pass using a hash map to break the visited-cycle problem.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
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 (int) and a list (List[Node]) of its neighbors.
Constraints
The number of nodes in the graph is in the range [0, 100].1 <= Node.val <= 100Node.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
Example 1
adjList = [[2,4],[1,3],[2,4],[1,3]][[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's neighbors are 1st node and 3rd node. And so on.
Example 2
adjList = [[]][[]]Explanation: Single node with no neighbors.
Example 3
adjList = [][]Explanation: Empty graph — no nodes.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
If you just DFS naively, cycles in the graph will trap you in infinite recursion. What state do you need to track?
Hint 2
Maintain a hash map from original node -> cloned node. Before recursing into a neighbor, check the map.
Hint 3
On first visit to a node: create its clone, store original->clone in the map, then recurse into each original neighbor to clone-or-fetch and append to the new node's neighbors list.
Solution approach
Reveal approach
DFS (or BFS) with a hash map from original-node to cloned-node. Base case: input is null -> return null. Define dfs(node): if node is in the map, return the cached clone (this is what breaks cycles); otherwise create a new node with the same val, store map[node] = clone immediately (so neighbors recursing back to this node see it as visited), then iterate node.neighbors and push dfs(neighbor) into clone.neighbors. Return clone. The early map-set is the trick — doing it after recursion would cause infinite cycles. O(V + E) time, O(V) space for the map plus recursion stack.
Complexity
- Time
- O(V + E)
- Space
- O(V)
Related patterns
- dfs
- bfs
- hash-map
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Meta
- Microsoft
- Bloomberg
Practice these live with InterviewChamp.AI
Drill Clone Graph and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →