Clone Graph (LeetCode 133): DFS with a Hash Map in Python

Clone Graph (LeetCode 133) asks you to return a deep copy of a connected undirected graph. The key idea is a hash map from each original node to its copy. It lets you create each copy once and wire up neighbors without looping forever on cycles. Time and space are O(V + E).

The problem

You get a reference to one node of a connected undirected graph. Each node has a value and a list of neighbors. Return a deep copy: new nodes with the same values and the same connections, and no node shared with the original. The input may be None, in which case return None.

The node class looks like this:

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

Why it isn't just a recursion

A graph can contain cycles, and in an undirected graph every edge is a tiny cycle (A lists B, and B lists A). A copy function that calls itself on every neighbor would never stop. You need to remember which nodes have already been copied.

Approach: map plus depth-first search

Keep a dictionary copies that maps an original node to its clone. Walk the graph with a stack. When you meet a neighbor you haven't copied, create its clone and push it. Either way, append the neighbor's clone to the current clone's neighbor list.

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

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    stack = [node]
    while stack:
        cur = stack.pop()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                stack.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

Trace

Take a square graph, 1 connected to 2 and 4, 2 to 3, 3 to 4. Start at node 1: create copy 1, then visit node 1's neighbors 2 and 4, creating copies for both and linking them to copy 1. Pop node 4: its neighbors are 1 and 3, so copy 1 is linked (already there), and copy 3 is created and linked. Pop node 3, then node 2, and the remaining links get added. Every node is created once, and every edge appears in both directions, because each endpoint adds the other to its own list.

Depth-first or breadth-first

Both work. Replace the stack with a deque and popleft() for breadth-first. The only requirement is the map. Recursion is shorter to write, but a deep graph can hit Python's recursion limit, so the iterative version is safer.

Common mistakes

• Making a new clone each time a node is seen, which duplicates nodes and loops forever.
• Copying the neighbor list by reference, so the clone points back at original nodes.
• Forgetting the None input.
• Using the node value as the map key when values aren't guaranteed unique. Using the node object itself is safer.

Edge cases to test

How to explain it in an interview

1. Say what a deep copy means here: new nodes, same shape.
2. Point out the cycles and why you need a map.
3. Describe the map from original to clone, and the traversal.
4. Write it, then walk through a two-node example.
5. State O(V + E) time and O(V) space.

I tested the code above on 3,000 random connected graphs, checking that the copy has the same values and edges and that no node is shared with the original, before publishing. A quick random check like that is a good habit when you practice.

Related practice

See our Big O cheat sheet for the complexity terms, the LeetCode Blind 75 list for what to practice next, and the coding interview assistant guide for how to practice.

Talk through your approach aloud while you code. A transcript shows whether you stated the key observation before writing. Follow the employer's rules on AI tools in any live assessment.