Clone Graph Leetcode Problem 133 [Python Solution]
In this post, we will explore the Clone Graph problem from LeetCode, specifically problem number 133. This is a medium difficulty problem that falls under the category of Graphs, and it is frequently associated with companies like Google.
If you'd like to access the original question on LeetCode, you can find it here.
Problem Overview
The problem statement provides us with a reference to a node in a connected undirected graph.
Our task is to return a deep copy (clone) of this graph.
Each node in the graph consists of an integer value and a list of its neighbors, which are also nodes.
To represent the graph, LeetCode uses an adjacency list.
This means that the graph is represented using unordered lists to describe the set of neighbors of each node.
The first node in the given list is always the starting node with a value of 1, and our goal is to return a reference to the cloned graph.
Example 1:
Let's take a look at an example to better understand the problem:
Input:
adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]
Output:
[[2, 4], [1, 3], [2, 4], [1, 3]]
Explanation:
In this example, there are 4 nodes in the graph.
The 1st node (val = 1) has neighbors with the 2nd node (val = 2) and the 4th node (val = 4).
The 2nd node (val = 2) has neighbors with the 1st node (val = 1) and the 3rd node (val = 3).
The 3rd node (val = 3) has neighbors with the 2nd node (val = 2) and the 4th node (val = 4).
The 4th node (val = 4) has neighbors with the 1st node (val = 1) and the 3rd node (val = 3).
This example demonstrates the structure of the graph we need to clone.
Understanding the Constraints
Before we delve into the solutions, let's understand the constraints given in the problem statement:
- The number of nodes in the graph is in the range [0, 100].
- The value of Node.val is between 1 and 100, and it is unique for each node.
- There are no repeated edges or self-loops in the graph.
- The graph is connected, and all nodes can be visited starting from the given node.
These constraints give us a good sense of the problem's scope and potential complexity.
Clone Graph LeetCode Problem Solution
Bruteforce Approach
One way to approach this problem is to use a depth-first search (DFS) algorithm.
We can create a copy of each node and its neighbors recursively.
To keep track of nodes and their copies, we can use a hash map.
Here's the Python code for this approach:
def cloneGraph(self, node: "Node") -> "Node":
oldToNew = {}
def dfs(node):
if node in oldToNew:
return oldToNew[node]
copy = Node(node.val)
oldToNew[node] = copy
for nei in node.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node) if node else None
In this solution, we define a function cloneGraph that takes the original node as an input and returns the cloned graph.
We maintain a oldToNew dictionary to map original nodes to their clones.
The dfs function is a recursive helper function that traverses the original graph.
If the node being explored already has a clone in our dictionary, we return that clone.
Otherwise, we create a copy of the node, add it to the dictionary, and recursively clone its neighbors.
The final return statement calls dfs on the input node (if it exists) and returns the cloned graph.
If the input node is None, it returns None.
This solution provides a deep copy of the graph by exploring the graph in a depth-first manner.
Time and Space Complexity
Now, let's analyze the time and space complexity of our solution.
- Time Complexity: The time complexity of this solution is
O(N + M), where N is the number of nodes and M is the number of edges in the graph.
This is because we visit each node and edge once during the depth-first traversal.
- Space Complexity: The space complexity is
O(N)because we use a dictionary to store the mapping of original nodes to their clones.
In the worst case, when all nodes are unique, this dictionary will have N entries.
Reasoning Behind Our Approach
The key insight behind this approach is to perform a depth-first search (DFS) to explore the graph while creating a clone for each node and its neighbors.
Using a hash map (oldToNew) allows us to keep track of which nodes have been cloned already, avoiding infinite loops in cases of cycles.
This approach ensures that we create an exact copy of the original graph, maintaining both the structure and the values of the nodes.
By recursively cloning neighbors, we build the entire cloned graph efficiently.
Related Interview Questions By Company:
- Find The Duplicate Number LeetCode
- Accounts Merge LeetCode
- Maximum Length Of A Concatenated String With Unique Characters
Related Interview Questions By Difficulty:
- Number Of Connected Components In An Undirected Graph LeetCode
- Shortest Path In Binary Matrix LeetCode
- Open The Lock LeetCode
Related Interview Questions By Category:
Conclusion
In this blog post, we've tackled the Clone Graph problem from LeetCode, offering a Python solution that utilizes depth-first search and a hash map to efficiently clone the graph.
We've explained the problem, provided a detailed solution, discussed the time and space complexity, and highlighted the reasoning behind our approach.
If you found this post helpful or have any questions or suggestions, please feel free to comment and share your thoughts.
We encourage you to explore more graph-related problems and continue your journey in mastering algorithmic problem-solving.
Happy coding!
