Skip to content

111 — Clone Graph

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

111 — Clone Graph

LeetCode 133 · Medium. Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains an integer value and a list of its neighbors.

🍽️ Intuition

Deep-copying a graph looks scarier than deep-copying a tree because a graph can have cycles — naively recursing "clone this node, then clone all its neighbors" will walk right back into a node you've already started cloning and recurse forever. The fix is the same trick used to keep any graph traversal from looping forever on a cycle: remember what you've already visited. The twist here is that "visited" isn't just a Bool — it needs to remember which clone corresponds to each original node, so that when node C is reached a second time (once from A, once from B), both paths wire up to the same clone instead of creating duplicates.

🚩 Pattern-Recognition Cue

"Return a deep copy of a graph, given a starting node and each node's neighbor list" is the cue: this is a graph traversal (DFS or BFS) where the "visit" action is "create a clone," and the visited-tracking structure doubles as a lookup table from original node to its clone — needed precisely because the graph can have cycles.

🐢 Brute Force

Traverse and clone correctly, but look up "have I already cloned this node, and if so, which clone?" by scanning a plain array of (original, clone) pairs — a linear scan instead of a dictionary.

class Node {
    var val: Int
    var neighbors: [Node?]
    init(_ val: Int) {
        self.val = val
        self.neighbors = []
    }
}

func cloneGraphBruteForce(_ node: Node?) -> Node? {
    guard let node = node else { return nil }
    var pairs: [(Node, Node)] = []   // linear-scan lookup instead of a dictionary

    func findClone(_ original: Node) -> Node? {
        for (orig, clone) in pairs {
            if orig === original { return clone }
        }
        return nil
    }

    func dfs(_ original: Node) -> Node {
        if let existing = findClone(original) { return existing }
        let clone = Node(original.val)
        pairs.append((original, clone))
        for case let neighbor? in original.neighbors {
            clone.neighbors.append(dfs(neighbor))
        }
        return clone
    }

    return dfs(node)
}

Big-O: with V nodes and E edges, every dfs call performs an O(V) scan through pairs, and dfs is invoked once per edge traversal — roughly O(V² + V·E).

🚀 Optimal

Same DFS shape, but the lookup table is a real dictionary keyed by the original node's val (unique per node, per the problem's constraints), giving an O(1) "have I cloned this already?" check.

func cloneGraph(_ node: Node?) -> Node? {
    guard let node = node else { return nil }
    var visited: [Int: Node] = [:]   // O(1) lookup by original node's val

    func dfs(_ original: Node) -> Node {
        if let existing = visited[original.val] { return existing }
        let clone = Node(original.val)
        visited[original.val] = clone
        for case let neighbor? in original.neighbors {
            clone.neighbors.append(dfs(neighbor))
        }
        return clone
    }

    return dfs(node)
}

// smoke test — build a 4-node cycle 1-2-3-4-1 and clone it
let n1 = Node(1), n2 = Node(2), n3 = Node(3), n4 = Node(4)
n1.neighbors = [n2, n4]
n2.neighbors = [n1, n3]
n3.neighbors = [n2, n4]
n4.neighbors = [n1, n3]

let clone = cloneGraph(n1)!
print(clone.val)                       // 1
print(clone === n1)                    // false — must be a fresh object
print(clone.neighbors.map { $0!.val }) // [2, 4]

Big-O: O(V + E) time — each node is cloned exactly once (O(1) dictionary write) and each edge is traversed exactly once. O(V) space for the dictionary plus the recursion stack.

🔑 The Key Insight

Both versions do the exact same recursive walk: clone this node, then recurse into each neighbor, wiring the clone's neighbor list as you go. The entire difference is the cost of answering "did I already clone this node?" — a question that must be asked before recursing, precisely because a graph (unlike a tree) can lead back to the same node via more than one path. The brute force answers it the hard way, scanning every pair cloned so far. The optimal version answers it in O(1) by keying a dictionary on the one piece of identity every node already carries — its val. Same traversal, same recursion tree shape, radically different cost per lookup.

🔗 Related Chapters

  • Graphs — this problem is the "visited set prevents infinite looping on a cycle" lesson from that chapter, with the visited set upgraded to a visited-to-clone map.
  • DFS and Backtracking — dfs recurses into every neighbor before returning, the same choose/recurse/return shape used throughout this batch (minus the "un-choose," since nothing here needs undoing).
  • Hash Maps and Hash Sets — the visited dictionary is the whole optimization: O(1) amortized lookup versus the brute force's O(V) linear scan.

🧸 Memory Sentence

Cloning a graph is DFS with a memory — a dictionary from original node to its clone, so a cycle that leads back to an already-cloned node reuses that clone instead of cloning forever.

✅ Check Your Understanding

  1. Why would a plain recursive clone without any visited tracking never terminate on the 4-node cycle in the example, even though the graph only has 4 nodes?
  2. The optimal solution keys visited on original.val. The real LeetCode problem guarantees all values are unique — what would break if they weren't, and what would you key on instead?
  3. Walk through dfs(n1) by hand: in what order do n1, n2, n3, n4 get inserted into visited, and at which specific call does the cycle get "caught" (i.e., visited[original.val] is found instead of a fresh clone being created)?

⬅️ Previous: Number of Islands · Next: Max Area of Island ➡️

Clone this wiki locally