Skip to main content
DSA patterns

Clone Graph

mediumGraphs Must-doMetaGoogleAmazon

Problem statement

You're given a reference to one node of a connected, undirected graph. Every node holds an integer value and a list of references to its neighbors. Build a completely independent copy of the whole graph — new node objects with the same values and the same connections — and return a reference to the copy of the given node.

This is the same problem as cloning a service topology: you have a reference to one node in a mesh of interconnected services, and you need a fully separate snapshot of the entire mesh — new objects, same structure — without accidentally sharing any node with the original.

Examples

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]

Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation: There are 4 nodes. Node 1 connects to nodes 2 and 4; node 2 connects to nodes 1 and 3; node 3 connects to nodes 2 and 4; node 4 connects to nodes 1 and 3. The cloned graph has the same 4 nodes wired together the same way, just as new objects.

Example 1

Example 2

Input: adjList = [[]]

Output: [[]]

Explanation: There's a single node with no neighbors, so its clone is a single node with no neighbors too.

Example 2

Example 3

Input: adjList = []

Output: []

Explanation: An empty graph — there's no starting node to clone, so the clone is also empty.

Hints

Hint 1: The graph is undirected, which means it can contain cycles (two nodes pointing back to each other, or longer loops). What happens if you try to clone neighbors recursively without remembering what you've already cloned?

Approach

Optimal: BFS with a hash map

Intuition

The same "clone once, remember it" idea works with an iterative, level-by-level traversal instead of recursion. This avoids relying on the call stack entirely, which matters for a graph large enough that deep recursion could hit a stack limit. The clone is created and registered in the map the moment a node is first discovered (either as the start node or as someone's neighbor) — the same "register before you explore further" rule as DFS, just enforced with a queue instead of the call stack.

Steps

  1. If the input node is empty, return empty.
  2. Clone the starting node right away and store the mapping original → clone in a hash map; push the original start node onto a queue.
  3. While the queue isn't empty:
    • Dequeue an original node cur.
    • For each of its neighbors: if the neighbor hasn't been cloned yet, clone it, store the mapping, and enqueue the original neighbor.
    • Either way, add the neighbor's clone to cur's clone's neighbor list.
  4. Return the clone of the starting node from the map.

Dry run

adjList = [[2],[1,3],[2]] — the same three-node line as before.

dequeued clone created this step clone's neighbor list built
1 (1 already cloned before the loop) clone(1).neighbors = [clone(2)] — clone(2) created here
2 (2 already cloned) clone(2).neighbors = [clone(1), clone(3)] — clone(3) created here
3 (3 already cloned) clone(3).neighbors = [clone(2)]

Same result as the DFS version, built level by level instead of by recursion.

Edge cases: an empty input returns empty before the queue is even created. A single node with no neighbors is cloned once, the queue empties on the first iteration with no neighbors to process, and its clone's neighbor list stays empty.

Complexity

Time O(V + E)

Space O(V)

from collections import deque
from typing import Optional


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


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

        old_to_new = {node: Node(node.val)}
        q = deque([node])

        while q:
            cur = q.popleft()
            for neighbor in cur.neighbors:
                if neighbor not in old_to_new:
                    old_to_new[neighbor] = Node(neighbor.val)
                    q.append(neighbor)
                old_to_new[cur].neighbors.append(old_to_new[neighbor])

        return old_to_new[node]


def build_graph(adj_list):
    if not adj_list:
        return None
    nodes = [Node(i + 1) for i in range(len(adj_list))]
    for i, neighbors in enumerate(adj_list):
        nodes[i].neighbors = [nodes[j - 1] for j in neighbors]
    return nodes[0]


def serialize(start):
    if start is None:
        return []
    visited = {}
    stack = [start]
    while stack:
        n = stack.pop()
        if n.val in visited:
            continue
        visited[n.val] = n
        for neighbor in n.neighbors:
            if neighbor.val not in visited:
                stack.append(neighbor)
    return [[nei.val for nei in visited[v].neighbors] for v in sorted(visited)]


def fmt(adj_list):
    return "[" + ",".join("[" + ",".join(map(str, row)) + "]" for row in adj_list) + "]"


if __name__ == "__main__":
    g1 = build_graph([[2, 4], [1, 3], [2, 4], [1, 3]])
    print(fmt(serialize(Solution().cloneGraph(g1))))

    g2 = build_graph([[]])
    print(fmt(serialize(Solution().cloneGraph(g2))))

    g3 = build_graph([])
    print(fmt(serialize(Solution().cloneGraph(g3))))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "deep copy a graph" — especially one described as connected or capable of having cycles
  • Idea: a hash map from original node to its clone; register the clone the moment a node is first seen, before recursing or enqueueing its neighbors
  • Cost: O(V + E) time and space — every node and every edge is visited once
  • Trap: creating a node's clone only after fully processing its neighbors, or checking the map after the fact instead of before recursing — either way, a cycle causes infinite recursion or duplicate clones

Interview follow-ups

  • The graph is too large to fit in memory alongside its clone. What would you do?

    You could clone the graph in place, one connected sub-region at a time, writing each cloned region out to storage before moving to the next and discarding the original once it's confirmed persisted — trading a single full-memory pass for a streaming one at the cost of extra I/O and needing a way to track which nodes have already been migrated across sub-region boundaries.

  • How would you verify that your clone is a true deep copy and not sharing any nodes with the original?

    Walk both graphs in lockstep from their respective start nodes (BFS or DFS works) and check two things at every node: the values match, and the cloned node is not the same object as the original node (an identity check, not a value check). If any node pair fails the identity check, some part of the clone still points into the original graph.

  • What if two different nodes could legitimately hold the same value?

    The hash map keys on the node object itself, not on its value, so this already works correctly — nothing in the algorithm assumes values are unique. This matters because a real topology can absolutely have two distinct nodes that happen to share a label or a value.

Frequently asked questions

That would only clone one layer — the new node's neighbor list would point at the original neighbor nodes, not new copies of them. Since the whole point is a fully independent copy, every reachable node has to be recreated, not just the one you started from.

Because the graph can have cycles. If node A and node B point to each other, cloning A means recursing into B, which recurses back into A. If A's clone isn't in the map yet at that point, the recursion clones A a second time and never terminates. Registering the clone the instant it's created — before touching its neighbors — is what breaks the cycle safely.

Both do the same amount of work with the same time and space complexity, so it's mostly a matter of taste and constraints. DFS reads slightly more compactly with recursion; BFS avoids recursion entirely, which is worth choosing if the graph could be large enough to risk a stack overflow on deep recursion.

Cloning a graph while correctly handling cycles is exactly the shape of problem you hit when snapshotting a live topology — a service mesh, a dependency graph, or a cluster of interconnected nodes — where you need an independent copy that won't be affected by later changes to the original, and where a naive copy would either miss connections or loop forever on a cyclic dependency.

The algorithm doesn't actually change — it never assumed the graph was undirected, only that each node exposes its outgoing neighbors. The same hash-map-first traversal correctly clones a directed graph, including one with cycles.