Watch 10 video solutions for Clone Graph, a medium level problem involving Hash Table, Depth-First Search, Breadth-First Search. This walkthrough by NeetCode has 264,469 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
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 in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:
Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.
Constraints:
[0, 100].1 <= Node.val <= 100Node.val is unique for each node.Problem Overview: You’re given a reference to a node in a connected undirected graph. Each node contains a value and a list of neighbors. The task is to return a deep copy of the entire graph. Every original node must be cloned exactly once, and all neighbor relationships must be preserved in the new graph.
The main challenge is handling cycles and shared neighbors. Graphs often contain loops, so blindly cloning neighbors can cause infinite recursion or duplicate nodes. The standard solution uses a hash map to store a mapping from each original node to its cloned counterpart.
Approach 1: Depth-First Search (DFS) for Graph Cloning (O(V + E) time, O(V) space)
This approach performs a recursive Depth-First Search starting from the given node. Maintain a hash map where the key is the original node and the value is the cloned node. When visiting a node, first check if it already exists in the map. If it does, return the existing clone. Otherwise, create a new node, store it in the map, then recursively clone each neighbor and append the results to the clone’s neighbor list.
The hash map prevents infinite loops when the graph contains cycles and ensures every node is cloned exactly once. The recursion naturally follows graph structure, making this approach concise and intuitive. Time complexity is O(V + E) because every vertex and edge is processed once. Space complexity is O(V) for the map and recursion stack.
Approach 2: Breadth-First Search (BFS) for Graph Cloning (O(V + E) time, O(V) space)
This version uses an iterative Breadth-First Search with a queue. Start by cloning the initial node and storing the mapping in a hash table. Push the original node into the queue. While the queue is not empty, pop a node, iterate through its neighbors, and clone any neighbor that hasn’t been seen before.
For each neighbor, either retrieve the existing clone from the map or create a new clone and push the original neighbor into the queue. Then append the cloned neighbor to the current node’s clone adjacency list. BFS avoids recursion depth limits and can be easier to reason about when debugging iterative graph traversal.
Recommended for interviews: Both DFS and BFS solutions are optimal with O(V + E) time complexity and O(V) space complexity. Interviewers typically expect a DFS solution first because it is shorter and clearly demonstrates understanding of graph traversal and memoization with a hash map. BFS is equally correct and shows you understand iterative graph processing and queue-based traversal.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(V + E) | O(V) | Common interview solution. Simple recursive structure and clear mapping from original nodes to cloned nodes. |
| Breadth-First Search (BFS) | O(V + E) | O(V) | Preferred when avoiding recursion depth limits or when implementing graph traversal iteratively with a queue. |