Clone Graph

PracticeNeetCode ↗LeetCode ↗

Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph. Every node holds a value and a list of neighbor references.

Example

Key Pointers

• A hashmap from original node → cloned node prevents infinite loops on cycles and stops any node from being cloned twice.
• DFS from the given node; the first time a node is seen, create and register its clone immediately, before recursing into its neighbors.
• Each neighbor list gets rebuilt naturally: for every original neighbor, recurse (or reuse an existing clone from the map) and append the result.

Step-by-Step Analysis

1. If the starting node is None, return None.
2. Create a hashmap old_to_new.
3. DFS(node): if node is already a key in the map, return its clone. Otherwise create a clone with an empty neighbor list, register it in the map, then for each original neighbor append dfs(neighbor) to the clone's list, and return the clone.
4. Call dfs on the starting node and return the result.

Complexity

Time: O(V + E) — Space: O(V)

Code

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: "Node") -> "Node":
    old_to_new = {}

    def dfs(n: "Node") -> "Node":
        if n in old_to_new:
            return old_to_new[n]
        copy = Node(n.val)
        old_to_new[n] = copy
        for neighbor in n.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy

    return dfs(node) if node else None

Code Explanation

How the solution above works, piece by piece.

1. old_to_new maps each original node to its copy; it doubles as the visited set.
2. If a node was already copied, return the existing copy. This is what stops cycles (1 → 2 → 3 → 4 → 1) from recursing forever.
3. Otherwise create the copy and register it in the map before recursing into neighbours.
4. For each neighbour, dfs(neighbor) returns its copy, which is appended to the copy's neighbour list.
5. Every node and edge is handled once: O(V + E) time and O(V) space.

Visual Walkthrough

Running it on the 4-node example [[2, 4], [1, 3], [2, 4], [1, 3]]:

Video Explanation

NeetCode — Clone Graph, LeetCode 133