Clone Graph medium
Description
Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph. Each node contains a value and a list of neighbours.
The node definition:
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors or []Examples
> Case 1:
Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]
Output: [[2, 4], [1, 3], [2, 4], [1, 3]]
# 4 nodes:
# 1 connected to 2, 4
# 2 connected to 1, 3
# 3 connected to 2, 4
# 4 connected to 1, 3
> Case 2:
Input: adjList = [[]]
Output: [[]] # one node, no neighbours
> Case 3:
Input: adjList = []
Output: [] # empty graphThe fundamental challenge
A graph can have cycles. If you just recursively copy each neighbour, you’ll loop forever as the recursion follows the cycle back to itself.
The fix: maintain a hash map {original_node: clone_node}. Before recursing on a neighbour, check the map. If the neighbour is already there, use the cached clone. Otherwise, create the clone, store it, then recurse.
This is the exact same idea as memoization from Day 5 — cache the result to avoid revisiting.
Approach 1: DFS with hash-map memo
Storing the clone in the map before recursing is critical. If you wait until after, the recursion will hit a cycle, fail to find the already-being-built node in the map, create another clone for it, and you’ll get duplicate nodes. The “create-then-store-then-recurse” sequence is the entire trick.
Approach 2: BFS variant
Same idea, but iteratively with a queue. Some find this easier to reason about because there’s no recursion to trace.
Why this problem matters
“DFS / BFS with a memo to avoid revisiting” is half of all graph algorithms in disguise. Once you’re comfortable with it, problems that sound completely different — Number of Distinct Subsequences, Reorder Routes, Walk a Bidirected Maze — all use the same shape.
It’s the single most reusable trick in graph problems. Memorize the pattern, not the problem.
Analysis
- Time: O(V + E) — each node is created once and each edge is traversed once.
- Space: O(V) for the hash map and the recursion stack / queue.