Clone Graph

Mediumbfs graphMetaAmazonGoogleMicrosoft

Given a reference of a node in a **connected undirected graph**, return a **deep copy** (clone) of the graph.

Each node in the graph contains a value (val) and a list of its neighbors (neighbors).

Examples

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

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

Explanation:There are 4 nodes in the graph. Node 1 connects to 2 and 4. Node 2 connects to 1 and 3. Node 3 connects to 2 and 4. Node 4 connects to 1 and 3.

Constraints

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.

💡 Hints

Hint 1

Use Breadth-First Search (BFS) with a queue and a hash map to map original nodes to their cloned counterparts.

Hint 2

For each neighbor of the current node, if it has not been cloned yet, clone it and push it to the queue.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear

Algorithmic Approach

Traverse the graph using BFS. Use a Hash Map to record visited nodes and store mapping from original node to cloned node.

Time ComplexityO(V + E)

Why:

BFS/DFS visits every unique node V and traverses each undirected edge E exactly once in O(V + E) time.

Space ComplexityO(V)

Why:

A hash map stores visited clones for up to V nodes, plus the traversal queue/stack holds up to V vertices.

Big-O Growth CurveLinear (O(N))

Execution time scales directly in proportion to the input size.

🌍 Real-World Use Cases

FigmaDocument Scene Graph Duplication

Deep-copying layers, vectors, and component hierarchy using graph BFS cloning.

🔍 Dry Run

Solution⏱ O(V + E) | 💾 O(V)

Queue / Frontier:

Line5

queue=[Node(1)]Array

clones.size=1number

Initialize queue with Node 1 and clone Node 1 into the hash map.