Problem 43 · Graphs

Clone Graph

MediumClassic DSA & systems

01Problem

Given a reference to a node in a connected undirected graph, return a deep copy where each node has a value and a list of neighbors.

02Key insight

Keep an old-to-new map that doubles as the visited set; create the clone when a node is first discovered so cycles resolve to the existing copy.

03Solution

solution.pypython22 lines

from __future__ import annotations
from collections import deque
from typing import Optional

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

def clone_graph(node: Optional[Node]) -> Optional[Node]:
    if node is None:
        return None
    clones: dict[Node, Node] = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        cur = queue.popleft()
        for nb in cur.neighbors:
            if nb not in clones:
                clones[nb] = Node(nb.val)
                queue.append(nb)
            clones[cur].neighbors.append(clones[nb])
    return clones[node]

Try it first.

TimeO(V+E)

SpaceO(V)

tests.py · 3 passing

tests.pypython6 lines

assert clone_graph(None) is None
a, b, c = Node(1), Node(2), Node(3)
a.neighbors, b.neighbors, c.neighbors = [b, c], [a, c], [a, b]
ca = clone_graph(a)
assert ca is not a and ca.val == 1 and [n.val for n in ca.neighbors] == [2, 3]
assert ca.neighbors[0].neighbors[0] is ca and ca.neighbors[0] is not b

04Staff-level follow-up

How do you snapshot a graph that is being mutated concurrently? Use copy-on-write/versioned nodes (MVCC) and clone at a read timestamp rather than locking the whole graph.