This problem follows the DFS + Hash Map pattern, commonly found in the Graphs category. Recognizing this pattern is key to solving it efficiently in an interview setting.
DFS traversal. Use a hash map to track original-to-clone mapping. Clone neighbors recursively.
The hash map serves double duty: it prevents infinite loops in cycles AND ensures each node is cloned exactly once.
cloned = {}
def cloneGraph(node):
if not node: return null
if node in cloned: return cloned[node]
clone = Node(node.val)
cloned[node] = clone
for neighbor in node.neighbors:
clone.neighbors.append(cloneGraph(neighbor))
return clonePractice Clone Graph and similar Graphs problems with flashcards. Build pattern recognition through active recall.
Practice this problem