Clone Graph
MediumDFS with a visited→copy map
Copy each node the first time you meet it, then follow its links to copy its neighbors.
The idea
Traverse the graph, and the first time you see a node create its copy and remember it in a map. Recurse into neighbors, wiring copies together; the map stops infinite loops.
Step 1 of 11. DFS clone: on first visit, copy the node into a map, then recurse into neighbours.
1/11
Optimal
timeO(V+E)spaceO(V)
One clone per original.
1function clone(node) {2 if (map.has(node)) return map.get(node);3 const copy = new Node(node.val);4 map.set(node, copy);5 for (const nb of node.neighbors)6 copy.neighbors.push(clone(nb));7 return copy;8}Input
- nodes
- 4, 4 edges
Memory
- cloned
- —
Output
- nodes
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- adjacency = [[2,4],[1,3],[2,4],[1,3]]
- Output:
- [[2,4],[1,3],[2,4],[1,3]]
- Explanation:
- A deep copy has the same shape and connections.
Example 2
- Input:
- adjacency = [[]]
- Output:
- [[]]
- Explanation:
- A single node with no neighbours.
Example 3
- Input:
- adjacency = []
- Output:
- []
- Explanation:
- Empty graph clones to empty.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.