This is our solution and implementation to problem #133: Clone Graph on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Clone Graph on LeetCode.
Problem Analysis
The problem gives us a graph node and asks us to perform a deep copy of the entire graph of the node, all of its connected nodes, their connected nodes, etc. Note that by deep copy, they indicate we must clone every node within the graph; we cannot return the same node as we are given, and we cannot return a graph where some nodes are cloned but others are not. To facilitate our analysis, we'll first look at a simpler problem: perform a deep copy of a tree starting with its root node. In this simpler problem, we can implement cloneTree to call itself recursively: it will clone the node it's given, then for each of its children, call itself and pass that child in as an argument. This is an example of a depth first search, and is similar to the approach we will take for the main problem. However, this approach will not work with all graphs, as it does not account for graphs which contain cycles. To account for this situation, we can use a Set to keep track of which nodes were visited so we can avoid visiting them again and thus avoid entering an infinite loop. Then, at each point in the traversal, clone each node only if it has not yet been cloned, and for each cloned node, append other cloned nodes in the same order as the original node's neighbors.
Implementation Strategy
In our implementation, we'll take a similar approach, but we'll use breadth-first search instead of depth-first search. We'll modify the normal breadth-first search algorithm to facilitate the cloning process. Our algorithm will use a hashMap to keep a mapping of nodes and cloned nodes, so that at any point, if we encounter a node we've seen before, we can directly access the cloned version which was previously created. At each iteration in the search, we'll iterate over the neighbors of the current node, and for each, we'll create a clone if it doesn't exist already, then append each cloned neighbor to the clone of the current node. The full algorithm can be summarized as:
- Create the map clonedNodes where the key is an original node and the value is a cloned node.
- Clone the first node and add it to clonedNodes.
- Create a queue nodesToVisit which will be used for the breadth-first search.
- Add the original node to nodesToVisit.
- While nodesToVisit is not empty:
- Dequeue from nodesToVisit and assign the node to currentNode.
- Get the clone of currentNode from clonedNodes and assign it to clonedCurrentNode.
- For each neighbor node neighbor of currentNode:
- Create a variable clonedNeighbor.
- If neighbor has already been cloned, assign the clone to clonedNeighbor.
- If not yet cloned:
- Create a new clone and assign it to clonedNeighbor.
- Add neighbor to nodesToVisit.
- Add clonedNeighbor to the list of neighbors in clonedCurrentNode.
- Return the cloned node of the original input node.
Space and Time Complexity
We will define the space and time complexity in terms of the number of vertices v and the number of edges e. The space complexity, including the cloned graph, is O(v+e), as the cloned graph will consume v+e space, the clone map will contain v key-value pairs, and the queue used in the breadth-first search will take up to v entries. The time complexity is O(v+e), which is the time complexity for any breadth-first search.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Solution.java file contains the main logic for the solution. Other files are used as utilities to support the main implementation.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.