Clone Graph

MEDIUM✓ CHIP-TIMEDLC #133 — FULL STATEMENT ↗

The drill: Deep-copy an undirected graph from a reference to one of its nodes — every node and every edge in the copy must be brand-new objects, never aliases back into the original graph.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A reference to a single node of a connected, undirected graph arrives — every other node is reachable from it through some chain of edges. The task is to produce a completely independent deep copy of that whole graph.

Every node and every edge in the copy has to be a fresh object; nothing in the clone may point back into the original structure, and the shape of connections has to match exactly, including any cycles the original graph contains.

Cycles are the real trap here — the same node can be reached again through a different path, and the clone still has to recognize it as the node it already built rather than duplicating it.

EX 01

node = []

→ []

EMPTY GRAPH

EX 02

node = [[]]

→ [[]]

SINGLE NODE, NO NEIGHBOURS

EX 03

node = [[2], [1]]

→ [[2], [1]]

TWO NODES, ONE EDGE

graph stays modest — no more than a few hundred nodes
the graph is connected and undirected; every node reaches every other
cycles are allowed and must be handled without infinite recursion
node values are unique, but the copy must use fresh objects, not the originals

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The graph may have cycles, so a naive recursive copy that doesn't remember what it's already built will recurse forever. What needs to be remembered per original node?

HINT 2 THE STRUCTURE

A map from original node to its clone, filled in the moment a node is first visited, turns cycles into simple lookups instead of infinite loops.

HINT 3 ONE STEP FROM THE ANSWER

Walk the graph from the start node: the first time you see an original node, create its clone and store it in the map immediately; then for every original neighbour, clone or reuse it from the map and wire it into the clone's neighbour list.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE MAPPED COPYPATTERN · DFS, CLONE ON FIRST VISITtriangle: 1↔2, 1↔3, 2↔3

STACK

— empty —

STEP 1

Triangle: 1↔2, 1↔3, 2↔3. The moment a node is first seen, its clone is created and mapped — cycles resolve to a lookup instead of infinite recursion.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/clone-graph.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def cloneGraph(self, node: Optional[Node]) -> Optional[Node]:
        clones = {}

        def dfs(n):
            if n in clones:
                return clones[n]
            copy = Node(n.val)
            clones[n] = copy
            for nb in n.neighbors:
                copy.neighbors.append(dfs(nb))
            return copy

        return dfs(node) if node else None

TIME O(V+E)SPACE O(V)PYTHON · RACE PACE · 14 LN

class Solution:
    def cloneGraph(self, node: Optional[Node]) -> Optional[Node]:
        if not node:
            return None

        clones = {node: Node(node.val)}
        queue = collections.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)

        # every clone now exists — a second pass safely wires up neighbours
        for original, clone in clones.items():
            clone.neighbors = [clones[nb] for nb in original.neighbors]
        return clones[node]

TIME O(V+E)SPACE O(V)PYTHON · TRAINING PACE · 18 LN

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        return dfs(node, new HashMap<>());
    }

    private Node dfs(Node n, Map<Node, Node> clones) {
        if (clones.containsKey(n)) return clones.get(n);
        Node copy = new Node(n.val);
        clones.put(n, copy);
        for (Node nb : n.neighbors) {
            copy.neighbors.add(dfs(nb, clones));
        }
        return copy;
    }
}

TIME O(V+E)SPACE O(V)JAVA · RACE PACE · 16 LN

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Map<Node, Node> clones = new HashMap<>();
        clones.put(node, new Node(node.val));
        Deque<Node> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (Node nb : cur.neighbors) {
                if (!clones.containsKey(nb)) {
                    clones.put(nb, new Node(nb.val));
                    queue.add(nb);
                }
            }
        }

        for (Map.Entry<Node, Node> entry : clones.entrySet()) {
            for (Node nb : entry.getKey().neighbors) {
                entry.getValue().neighbors.add(clones.get(nb));
            }
        }
        return clones.get(node);
    }
}

TIME O(V+E)SPACE O(V)JAVA · TRAINING PACE · 26 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED