Leetcode 133. Clone Graph
Asked at:
Meta
DESCRIPTION
Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a value (val) and a list of its neighbors (neighbors). The clone must preserve the graph's structure, including cycles and shared neighbors, ensuring each original node maps to exactly one unique cloned node. For example, if node 1 connects to nodes 2 and 3, and node 2 also connects to node 3, the cloned graph must maintain these exact relationships.
Input:
adjList = [[2,4],[1,3],[2,4],[1,3]] 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
Output:
A cloned graph with the same structure: Cloned node 1 connects to cloned nodes 2 and 4 Cloned node 2 connects to cloned nodes 1 and 3 Cloned node 3 connects to cloned nodes 2 and 4 Cloned node 4 connects to cloned nodes 1 and 3
Explanation: Each node in the original graph has a corresponding clone with identical neighbor relationships preserved
Constraints:
- The number of nodes in the graph is in the range [0, 100]
- Node values are unique: 1 <= Node.val <= 100
- The graph is connected (all nodes are reachable from the given node)
- The graph is undirected (if node A connects to node B, then node B connects to node A)
- There are no self-loops or duplicate edges
Understanding the Problem
The core challenge is avoiding duplicate clones when traversing a graph with cycles and shared neighbors. If we naively clone each neighbor recursively, we'll create multiple copies of the same node and enter infinite loops on cycles. We need a mapping structure to track which original nodes have already been cloned, ensuring each node is cloned exactly once. The solution requires graph traversal (DFS or BFS) combined with a hash map to store the original-to-clone correspondence.
Building Intuition
A naive recursive approach would clone each node and recursively clone its neighbors, but this fails on cycles (infinite recursion) and shared neighbors (duplicate clones). The key insight is to use a hash map to track cloned nodes: before cloning a neighbor, check if it's already been cloned. If yes, reuse the existing clone; if no, create a new clone and add it to the map. For example, when cloning a square graph (1-2-3-4-1), after cloning node 1 and its neighbor node 2, when we later encounter node 1 as a neighbor of node 4, we retrieve the existing clone from the map instead of creating a duplicate.
Graph cloning is fundamental in serialization/deserialization systems, state management (creating snapshots of complex object graphs), and distributed systems (replicating data structures across nodes). Understanding how to preserve object identity and relationships during deep copying is crucial for implementing copy-on-write semantics, undo/redo functionality, and graph databases.
Common Pitfalls
Implementation
DFS Traversal with Clone Mapping
Implement a recursive depth-first search that clones nodes while maintaining a HashMap<Node, Node> to map original nodes to their clones. For each node, create its clone immediately and store it in the map before processing neighbors (this prevents infinite recursion on cycles). Then recursively clone each neighbor, checking the map first to reuse existing clones. For example, when cloning a triangle graph (1-2-3-1), after cloning node 1 and recursively cloning neighbor 2, when node 2 tries to clone neighbor 1, it finds the existing clone in the map and reuses it.
def cloneGraph(node, clone_map=None):if not node:return Noneif clone_map is None:clone_map = {}if node in clone_map:return clone_map[node]clone = Node(node.val)clone_map[node] = clonefor neighbor in node.neighbors:clone.neighbors.append(cloneGraph(neighbor, clone_map))return clone
BFS Traversal Alternative
Implement an iterative breadth-first search using a Queue for level-order traversal and the same clone mapping strategy from the DFS approach. Start by cloning the input node and adding it to both the queue and the map. For each node dequeued, iterate through its neighbors: if a neighbor hasn't been cloned yet, create its clone, add to the map, and enqueue it for later processing. Then connect the current clone to each neighbor's clone. For example, in a star graph (center node connected to 4 leaf nodes), the BFS processes the center first, clones all leaves in one pass, then connects them without revisiting any node.
from collections import dequedef cloneGraphBFS(node):if not node:return Noneclone_map = {node: Node(node.val)}queue = deque([node])while queue:current = queue.popleft()for neighbor in current.neighbors:if neighbor not in clone_map:clone_map[neighbor] = Node(neighbor.val)queue.append(neighbor)clone_map[current].neighbors.append(clone_map[neighbor])return clone_map[node]
Complete Integration
Combine both traversal approaches into a unified solution interface that demonstrates when to use each method. The DFS approach (Section 1) is more memory-efficient for deep graphs due to implicit stack usage, while the BFS approach (Section 2) is better for shallow, wide graphs and provides level-order processing. Show a wrapper that selects the appropriate strategy based on graph characteristics, or provides both as alternative implementations. For example, create a GraphCloner class that exposes both cloneDFS(node) and cloneBFS(node) methods, allowing users to choose based on their specific graph structure and memory constraints.
class GraphCloner:def __init__(self):passdef cloneDFS(self, node):"""Memory-efficient for deep graphs"""return cloneGraph(node)def cloneBFS(self, node):"""Better for shallow, wide graphs"""return cloneGraphBFS(node)def clone(self, node, prefer_bfs=False):"""Auto-select strategy based on preference"""return self.cloneBFS(node) if prefer_bfs else self.cloneDFS(node)
What We've Learned
- Pattern: Use a hash map to track visited nodes during graph traversal to prevent duplicate processing and handle cycles
- Use Case: Apply this clone mapping technique to deep copy any object graph with circular references (linked lists with cycles, tree parent pointers, bidirectional relationships)
- Trade-off: DFS uses less memory (implicit call stack) but risks stack overflow on deep graphs; BFS uses explicit queue but handles deep graphs safely
- Critical Step: Always add node to visited map before processing neighbors to correctly handle back-edges and self-references
Problems to Practice
easy
This is essentially the same problem as Clone Graph (LeetCode 133). It requires creating a deep copy of a graph while preserving all connections and handling cycles, using DFS traversal with a hash map to track visited nodes.
This lesson covers graph representation using adjacency lists, which is the fundamental data structure used in the Clone Graph problem. Understanding how graphs are represented is essential for solving graph cloning problems.
medium
This problem also involves graph traversal with cycle detection and uses similar techniques of tracking visited nodes during DFS. It reinforces understanding of graph connectivity and traversal patterns needed for cloning graphs.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late April, 2026
Meta
Senior
Mid December, 2025
Junior
Late November, 2025
Meta
Staff
Hello Interview Premium
Your account is free and you can post anonymously if you choose.