Clone Graph 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Given a reference to a node in a connected undirected graph, return a deep copy. The key insight is using a hashmap to track cloned nodes and avoid infinite loops.

# Map: original node -> cloned node
# DFS: for each node, create clone, recursively clone neighbors
# If neighbor already cloned (in map), reuse it

Create hashmap: old_node → new_node
DFS: clone each node, recursively clone all neighbors
Time: O(V+E), Space: O(V)

💡 Pro tip: Understand this problem deeply — don't just memorize the code. Try explaining the approach out loud as if teaching a friend. If you can explain it simply, you truly understand it!

📋 Instructions

Simulate graph cloning with adjacency list. Given adj = {1: [2,4], 2: [1,3], 3: [2,4], 4: [1,3]}, deep copy it and print sorted adjacency list.

Use a dict for cloned. DFS recursion: if node not in cloned, add it and recurse on each neighbor.

🧪 Test Cases

Input

Run your code

Expected

1: [2, 4]
2: [1, 3]
3: [2, 4]
4: [1, 3]

Expected program output

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›