Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Clone Graph
• Topics: Hash Table, Depth-First Search, Breadth-First Search, Graph Theory

Problem gist

The input is a reference to one node in a connected, undirected graph. Each node stores a value and a list of neighboring nodes. The goal is to return a deep copy of the entire graph: every original node must have a newly created counterpart, and every edge must connect the corresponding copied nodes.

Copying a graph is more subtle than copying a tree. A graph can contain cycles, so blindly following neighbors may loop forever. Multiple nodes can also point to the same neighbor, so creating a fresh copy every time that neighbor is encountered would incorrectly duplicate one logical node.

The key is to remember exactly one clone for every original node.

Deriving the traversal and clone map

Start with the given node and traverse the graph using breadth-first search. Maintain a map whose keys are original nodes and whose values are their clones.

For each original node removed from the queue:

1. Examine each of its neighbors.
2. If a neighbor has not been seen, create its clone, save it in the map, and add the original neighbor to the queue.
3. Append the neighbor’s saved clone to the current clone’s neighbor list.

Creating a clone and marking the original as discovered happen at the same time. That ordering matters: if two nodes both lead to the same unseen neighbor, the first encounter records its clone before another encounter can create a duplicate.

The map serves two purposes at once. It is the traversal’s visited set, which prevents cycles from causing repeated work, and it preserves the one-to-one relationship between original nodes and copied nodes.

Breadth-first search and depth-first search are both optimal here. Breadth-first search is a practical default because it avoids recursion-depth limits on long graphs.

Python solution

from collections import deque
from typing import Optional


# LeetCode provides this class definition:
# class Node:
#     def __init__(self, val: int = 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"]:
        """Return a deep copy of the connected component containing node."""
        if node is None:
            return None

        return self._clone_connected_component(node)

    @staticmethod
    def _clone_connected_component(start: "Node") -> "Node":
        # Recording a clone when its original is discovered guarantees that
        # cycles and shared neighbors never create duplicate nodes.
        clone_by_original: dict["Node", "Node"] = {
            start: Node(start.val)
        }
        originals_to_visit = deque([start])

        while originals_to_visit:
            original = originals_to_visit.popleft()
            original_clone = clone_by_original[original]

            for original_neighbor in original.neighbors:
                if original_neighbor not in clone_by_original:
                    clone_by_original[original_neighbor] = Node(
                        original_neighbor.val
                    )
                    originals_to_visit.append(original_neighbor)

                # Rebuild the edge using clones, never original nodes.
                original_clone.neighbors.append(
                    clone_by_original[original_neighbor]
                )

        return clone_by_original[start]

Complexity

Let V be the number of nodes reachable from the input node and E be the number of edges among them.

• Time: O(V + E). Each node is processed once, and every neighbor-list entry is examined once. In an undirected graph, each edge appears in two neighbor lists, which is still O(E).
• Auxiliary space: O(V). The clone map stores one entry per node, and the queue can hold up to O(V) nodes. The returned cloned graph itself requires O(V + E) output space.

Interview follow-ups

Could this be implemented with depth-first search instead?

Yes. A recursive function first checks the clone map. If the original node already has a clone, it returns that clone immediately. Otherwise, it creates and records the clone before recursively cloning the neighbors, then fills the clone’s neighbor list with the recursive results.

Recording the clone before recursion is what breaks cycles. DFS still takes O(V + E) time and uses O(V) for the map. Its call stack may also grow to O(V), which can overflow Python’s recursion limit on a long chain; iterative BFS or DFS avoids that production risk.

What if the input contains several disconnected components?

A single starting node cannot reveal disconnected components, so the API would need to receive every node or another representation that lists the entire graph. Iterate through that collection and start a traversal whenever a node is absent from the shared clone map. All traversals must use the same map so cross-references are cloned consistently if the input representation contains them.

The total cost remains O(V + E) because every node and edge is processed once across all components. The additional traversal loop costs O(V) and does not change the overall bound.

Can values be used as keys instead of node objects?

Only if node values are guaranteed to be unique. The standard problem makes that guarantee, but object identity is the safer general solution: two distinct graph nodes can legitimately carry the same value in a production model.

Using the original node object as the key directly represents the relationship being preserved and needs no extra uniqueness assumption. If node objects are not hashable, assign stable IDs or keep an identity-based map supplied by the graph model; searching a list for every encounter would degrade the running time toward O(V^2 + E).

How would the approach change for a directed or weighted graph?

The traversal and clone map do not fundamentally change. For a directed graph, copy only the outgoing adjacency entries that are present; no reverse edge should be invented. For a weighted graph, each adjacency entry must include both the cloned destination and the original edge’s weight or metadata.

Each node and adjacency entry is still copied once, so the running time is O(V + E) and the traversal’s auxiliary space is O(V). Rich edge objects increase output size but not the asymptotic complexity.

Can the graph be cloned with less than linear auxiliary space?

Not in the general case without temporarily modifying the original graph or relying on restrictive graph structure. Cycles and shared neighbors require a way to find the one existing clone for an already encountered original node. The clone map provides that lookup in constant expected time and needs one entry per node.

Temporary pointer-weaving techniques can remove a separate map for special structures such as linked lists, but arbitrary graphs do not provide a safe universal place to store and later recover those links. O(V) auxiliary space is therefore the standard practical tradeoff for a non-mutating clone.