133. Clone Graph (Medium)

Problem

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node has a value and a list of its neighbors.

LeetCode 133 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: DFS + hash map old -> new

Walk the graph recursively; keep a dict mapping each original node to its clone. On each node, create the clone, then recursively clone neighbors.

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

def clone_graph(node):
    if not node:                               # L1: O(1) null guard
        return None
    old_to_new = {}                            # L2: O(1) init map

    def dfs(n):
        if n in old_to_new:                    # L3: O(1) already cloned
            return old_to_new[n]
        copy = Node(n.val)                     # L4: O(1) create clone
        old_to_new[n] = copy                   # L5: O(1) register before recursing (cycle safety)
        for nb in n.neighbors:
            copy.neighbors.append(dfs(nb))     # L6: O(1) per edge, recurse each neighbor
        return copy

    return dfs(node)

class Node {
    val: number;
    neighbors: Node[];
    constructor(val: number = 0, neighbors: Node[] = []) {
        this.val = val;
        this.neighbors = neighbors;
    }
}

function cloneGraph(node: Node | null): Node | null {
    if (!node) return null;                    // L1: O(1) null guard
    const oldToNew = new Map<Node, Node>();    // L2: O(1) init map

    function dfs(n: Node): Node {
        if (oldToNew.has(n)) return oldToNew.get(n)!;  // L3: O(1) already cloned
        const copy = new Node(n.val);          // L4: O(1) create clone
        oldToNew.set(n, copy);                 // L5: O(1) register before recursing (cycle safety)
        for (const nb of n.neighbors) {
            copy.neighbors.push(dfs(nb));      // L6: O(1) per edge, recurse each neighbor
        }
        return copy;
    }

    return dfs(node);
}

func cloneGraph(node *Node) *Node {
    if node == nil {                             // L1: O(1) null guard
        return nil
    }
    oldToNew := map[*Node]*Node{}               // L2: O(1) init map

    var dfs func(n *Node) *Node
    dfs = func(n *Node) *Node {
        if c, ok := oldToNew[n]; ok {           // L3: O(1) already cloned
            return c
        }
        copy := &Node{Val: n.Val}               // L4: O(1) create clone
        oldToNew[n] = copy                      // L5: O(1) register before recursing
        for _, nb := range n.Neighbors {
            copy.Neighbors = append(copy.Neighbors, dfs(nb)) // L6: recurse each neighbor
        }
        return copy
    }

    return dfs(node)
}

func makeGraph(_ adjacency: [[Int]]) -> Node? {
    guard !adjacency.isEmpty else { return nil }
    let nodes = adjacency.indices.map { Node($0 + 1) }
    for index in adjacency.indices {
        nodes[index].neighbors = adjacency[index].map { nodes[$0 - 1] }
    }
    return nodes[0]
}

func isValidClone(_ original: Node?, _ clone: Node?, _ expected: [[Int]]) -> Bool {
    if expected.isEmpty { return original == nil && clone == nil }
    guard let original, let clone else { return false }
    var originalIDs = Set<ObjectIdentifier>()
    var originalQueue = [original], originalHead = 0
    while originalHead < originalQueue.count {
        let node = originalQueue[originalHead]; originalHead += 1
        if !originalIDs.insert(ObjectIdentifier(node)).inserted { continue }
        originalQueue.append(contentsOf: node.neighbors.compactMap { $0 })
    }
    var rows = Array(repeating: [Int](), count: expected.count)
    var seen = Set<ObjectIdentifier>(), queue = [clone], head = 0
    while head < queue.count {
        let node = queue[head]; head += 1
        let id = ObjectIdentifier(node)
        if !seen.insert(id).inserted { continue }
        if originalIDs.contains(id) || node.val < 1 || node.val > expected.count { return false }
        rows[node.val - 1] = node.neighbors.compactMap { $0?.val }
        queue.append(contentsOf: node.neighbors.compactMap { $0 })
    }
    return seen.count == expected.count && rows == expected
}

final class Solution {
    func cloneGraph(_ node: Node?) -> Node? {
        guard let node else { return nil }
        var copies: [ObjectIdentifier: Node] = [:]
        func clone(_ current: Node) -> Node {
            let key = ObjectIdentifier(current)
            if let copy = copies[key] { return copy }
            let copy = Node(current.val)
            copies[key] = copy
            copy.neighbors = current.neighbors.map { $0.map(clone) }
            return copy
        }
        return clone(node)
    }
}

Where the time goes, line by line

Variables: V = number of nodes in the graph, E = number of edges.

Line	Per-call cost	Times executed	Contribution
L3 (cache hit check)	$O(1)$	V total across all calls	$O(V)$
L4 (create clone)	$O(1)$	V (one per node)	$O(V)$
L5 (register in map)	$O(1)$	V	$O(V)$
L6 (neighbor loop)	$O(1)$ per edge	E total across all calls	$O(E)$ ← dominates for dense graphs

Each node is created exactly once (L3 short-circuits revisits). Each edge is traversed exactly once per direction in an undirected graph, so the neighbor loop across all nodes totals $O(E)$ . The map lookup/insert at L3/L5 is $O(1)$ average for a hash map. Total: $O(V + E)$ .

Complexity

Time: $O(V + E)$ , driven by L6 (each edge visited once per direction).
Space: $O(V)$ for the hash map, plus $O(V)$ recursion stack depth in the worst case (a path graph).

Canonical, cleanest.

Approach 2: BFS + hash map

Same idea, queue-driven; useful when recursion depth is a concern.

from collections import deque

def clone_graph(node):
    if not node:                               # L1: O(1) null guard
        return None
    old_to_new = {node: Node(node.val)}        # L2: O(1) seed map with root
    q = deque([node])                          # L3: O(1) init queue
    while q:                                   # L4: loop until queue empty
        cur = q.popleft()                      # L5: O(1) dequeue
        for nb in cur.neighbors:               # L6: O(degree) per node
            if nb not in old_to_new:
                old_to_new[nb] = Node(nb.val)  # L7: O(1) create clone once
                q.append(nb)                   # L8: O(1) enqueue for later
            old_to_new[cur].neighbors.append(old_to_new[nb])  # L9: O(1) wire edge
    return old_to_new[node]

function cloneGraph(node: Node | null): Node | null {
    if (!node) return null;                              // L1: O(1) null guard
    const oldToNew = new Map<Node, Node>();
    oldToNew.set(node, new Node(node.val));             // L2: O(1) seed map with root
    const q: Node[] = [node];                           // L3: O(1) init queue
    let head = 0;
    while (head < q.length) {                           // L4: loop until queue empty
        const cur = q[head++];                          // L5: O(1) dequeue
        for (const nb of cur.neighbors) {               // L6: O(degree) per node
            if (!oldToNew.has(nb)) {
                oldToNew.set(nb, new Node(nb.val));     // L7: O(1) create clone once
                q.push(nb);                             // L8: O(1) enqueue for later
            }
            oldToNew.get(cur)!.neighbors.push(oldToNew.get(nb)!);  // L9: O(1) wire edge
        }
    }
    return oldToNew.get(node)!;
}

func cloneGraph(node *Node) *Node {
    if node == nil {                                       // L1: O(1) null guard
        return nil
    }
    oldToNew := map[*Node]*Node{node: {Val: node.Val}}    // L2: O(1) seed map with root
    queue := []*Node{node}                                // L3: O(1) init queue
    for len(queue) > 0 {                                  // L4: loop until queue empty
        cur := queue[0]; queue = queue[1:]                // L5: O(1) dequeue
        for _, nb := range cur.Neighbors {                // L6: O(degree) per node
            if _, ok := oldToNew[nb]; !ok {
                oldToNew[nb] = &Node{Val: nb.Val}         // L7: O(1) create clone once
                queue = append(queue, nb)                 // L8: O(1) enqueue for later
            }
            oldToNew[cur].Neighbors = append(oldToNew[cur].Neighbors, oldToNew[nb]) // L9: wire edge
        }
    }
    return oldToNew[node]
}

func makeGraph(_ adjacency: [[Int]]) -> Node? {
    guard !adjacency.isEmpty else { return nil }
    let nodes = adjacency.indices.map { Node($0 + 1) }
    for index in adjacency.indices {
        nodes[index].neighbors = adjacency[index].map { nodes[$0 - 1] }
    }
    return nodes[0]
}

func isValidClone(_ original: Node?, _ clone: Node?, _ expected: [[Int]]) -> Bool {
    if expected.isEmpty { return original == nil && clone == nil }
    guard let original, let clone else { return false }
    var originalIDs = Set<ObjectIdentifier>()
    var originalQueue = [original], originalHead = 0
    while originalHead < originalQueue.count {
        let node = originalQueue[originalHead]; originalHead += 1
        if !originalIDs.insert(ObjectIdentifier(node)).inserted { continue }
        originalQueue.append(contentsOf: node.neighbors.compactMap { $0 })
    }
    var rows = Array(repeating: [Int](), count: expected.count)
    var seen = Set<ObjectIdentifier>(), queue = [clone], head = 0
    while head < queue.count {
        let node = queue[head]; head += 1
        let id = ObjectIdentifier(node)
        if !seen.insert(id).inserted { continue }
        if originalIDs.contains(id) || node.val < 1 || node.val > expected.count { return false }
        rows[node.val - 1] = node.neighbors.compactMap { $0?.val }
        queue.append(contentsOf: node.neighbors.compactMap { $0 })
    }
    return seen.count == expected.count && rows == expected
}

final class Solution {
    func cloneGraph(_ node: Node?) -> Node? {
        guard let node else { return nil }
        let root = Node(node.val)
        var copies = [ObjectIdentifier(node): root]
        var queue = [node], head = 0
        while head < queue.count {
            let current = queue[head]; head += 1
            let copy = copies[ObjectIdentifier(current)]!
            for neighbor in current.neighbors {
                guard let neighbor else { copy.neighbors.append(nil); continue }
                let key = ObjectIdentifier(neighbor)
                if copies[key] == nil { copies[key] = Node(neighbor.val); queue.append(neighbor) }
                copy.neighbors.append(copies[key]!)
            }
        }
        return root
    }
}

Where the time goes, line by line

Variables: V = number of nodes in the graph, E = number of edges.

Line	Per-call cost	Times executed	Contribution
L2, L3 (init)	$O(1)$	1	$O(1)$
L5 (dequeue)	$O(1)$	V	$O(V)$
L7 (create clone)	$O(1)$	V	$O(V)$
L8 (enqueue)	$O(1)$	V	$O(V)$
L6, L9 (edge wiring)	$O(1)$ per edge	E total	$O(E)$ ← dominates for dense graphs

Each node is enqueued and dequeued exactly once. Each edge is wired at L9 exactly once per direction. The queue size is bounded by $O(V)$ in the worst case (a star graph where the center fans out to all other nodes).

Complexity

Time: $O(V + E)$ , driven by L6/L9 (iterating every edge).
Space: $O(V)$ for the map and queue.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Notes
DFS + old->new map	$O(V + E)$	$O(V)$	Canonical
BFS + old->new map	$O(V + E)$	$O(V)$	Avoids deep recursion

All three are optimal in Big-O. DFS is the shortest to write.

# Quick smoke tests, paste into a REPL or save as test_133.py and run.
# Uses the canonical implementation (Approach 1: DFS + hash map).

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

def clone_graph(node):
    if not node:
        return None
    old_to_new = {}

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

    return dfs(node)

def _run_tests():
    # Null input
    assert clone_graph(None) is None

    # Single node, no neighbors
    n1 = Node(1)
    c1 = clone_graph(n1)
    assert c1 is not n1
    assert c1.val == 1
    assert c1.neighbors == []

    # Two nodes connected to each other: 1 -- 2
    a = Node(1)
    b = Node(2)
    a.neighbors = [b]
    b.neighbors = [a]
    ca = clone_graph(a)
    assert ca is not a
    assert ca.val == 1
    assert len(ca.neighbors) == 1
    cb = ca.neighbors[0]
    assert cb is not b
    assert cb.val == 2
    assert cb.neighbors[0] is ca  # back-pointer points to clone, not original

    # Four-node cycle: 1-2-3-4-1, each node also connected to the diagonal
    # adjacency: 1:[2,4], 2:[1,3], 3:[2,4], 4:[3,1]
    nodes = [Node(i) for i in range(1, 5)]
    nodes[0].neighbors = [nodes[1], nodes[3]]
    nodes[1].neighbors = [nodes[0], nodes[2]]
    nodes[2].neighbors = [nodes[1], nodes[3]]
    nodes[3].neighbors = [nodes[2], nodes[0]]
    root_clone = clone_graph(nodes[0])
    # Collect all cloned nodes by BFS on the clone
    from collections import deque
    visited = {}
    q = deque([root_clone])
    while q:
        cur = q.popleft()
        if cur.val in visited:
            continue
        visited[cur.val] = cur
        for nb in cur.neighbors:
            q.append(nb)
    assert set(visited.keys()) == {1, 2, 3, 4}
    # No clone should be an original node
    for orig in nodes:
        assert orig not in visited.values()

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

class Node {
    val: number;
    neighbors: Node[];
    constructor(val: number = 0, neighbors: Node[] = []) {
        this.val = val;
        this.neighbors = neighbors;
    }
}

function cloneGraph(node: Node | null): Node | null {
    if (!node) return null;
    const oldToNew = new Map<Node, Node>();

    function dfs(n: Node): Node {
        if (oldToNew.has(n)) return oldToNew.get(n)!;
        const copy = new Node(n.val);
        oldToNew.set(n, copy);
        for (const nb of n.neighbors) copy.neighbors.push(dfs(nb));
        return copy;
    }

    return dfs(node);
}

const n1 = new Node(1);
const c1 = cloneGraph(n1)!;
console.assert(c1 !== n1);
console.assert(c1.val === 1);
console.assert(c1.neighbors.length === 0);

const a = new Node(1);
const b = new Node(2);
a.neighbors = [b];
b.neighbors = [a];
const ca = cloneGraph(a)!;
console.assert(ca !== a && ca.val === 1);
const cb = ca.neighbors[0];
console.assert(cb !== b && cb.val === 2 && cb.neighbors[0] === ca);

console.assert(cloneGraph(null) === null);
console.log("all tests pass");

Hash Tables, old -> new node mapping
Queues, BFS variant

DFS, depth-first traversal tactics for exploring one branch fully before backtracking to alternatives.
Graph Traversal, visited-state tactics for exploring nodes, edges, components, and reachability relationships.

133. Clone Graph (Medium)

Problem

Try it yourself

Approach 1: DFS + hash map old -> new

Approach 2: BFS + hash map

Summary

Test cases

Related data structures

Related concepts