It is Friday morning and I am getting on Skype to chat with my best friend. We met when we were attending elementary school. We chat most Fridays but sometimes something comes up and we need to postpone for the following week. All friendships need care and time to maintain. The call occurs at 06:00 AM so hopefully I will have time to get this post done before the call.
The weekend is going to be the warmest of the year so far. We will be around 60F. Most people are going to use their grills or smokers. I believe we will join the group.
I received a message associated with a previous post. I will reply to it later today. The message suggests some improvements to my code. First of all I appreciate the message and suggestion. Please note that in general I want to get a solution up and running and accepted by the web site (e.g., HackerRank, LeetCode). If the solution is too slow, in general I try a second and in some occasions a third approach. I am not going to say that I have the best possible solution. I just want to make sure I describe my approach and you can see my thought process.
Please keep in mind that in most web sites, after you get your code accepted, you can see the source code accepted for different solutions. In the case of LeetCode, you can even see the code for the fastest solution. Most of the time, I take a look at the best solutions, because I can always learn something new. So, please make a note that, once you have an accepted solution, you could possibly cut and paste it and submit it. I do not see the gain of such approach.
OK, enough chit-chat and let’s get down to the main subject of this post. I decided to give a try to LeetCode problem 133 Clone Graph. The idea is given the first node in a graph we need to generate a deep copy of it. A deep copy is a clone (not a shallow) copy of the graph.
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 val (int) and a list (List[Node]) of its neighbors. Constraints: o 1 <= Node.val <= 100 o Node.val is unique for each node. o Number of Nodes will not exceed 100. o There is no repeated edges and no self-loops in the graph. o The Graph is connected and all nodes can be visited starting from the given node.
Note that the graph is undirected. This means that edges are bidirectional. If there is an edge between nodes 1 and 2 you can traverse the nodes from 1 to 2 of from 2 to 1.
We are going to use the Java programming language to solve this problem on my computer using the VSCode IDE. That said; the simplest approach is to solve the problem on-line using the IDE provided by LeetCode. I like to have the test scaffolding and the solution together so I can continue to experiment with the problem in the future. Because of this we will have to create test code which IS NOT PART OF THE SOLUTION.
class Node {
public int val;
public List<Node> neighbors;
}
The Node class must be used to implement the solution as stated by the requirements.
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
}
}
LeetCode also provides some constructors. Seems reasonable based on the constraints. Towards the end of the code snippet we are provided the signature for the method in question.
Test case format: For simplicity sake, 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. 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.
The format for the test case is also provided. I believe the information is quite useful and takes the place of a customer informing what is required. That is typically the job of system analysts.
Input: adjList = [2,4],[1,3],[2,4],[1,3] main <<< len: 4 main <<< str ==>2,4<== main <<< str ==>1,3<== main <<< str ==>2,4<== main <<< str ==>1,3<== main <<< x: [2, 4] main <<< x: [1, 3] main <<< x: [2, 4] main <<< x: [1, 3] main <<< graph: 2 4 1 3 2 4 3 1 main <<< clone: 2 4 1 3 2 4 3 1 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). Input: adjList = [] main <<< len: 1 main <<< graph: main <<< clone: 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. Input: adjList = main <<< len: 1 main <<< graph: null main <<< clone: null Explanation: This an empty graph, it does not have any nodes. Input: adjList = [2],[1] main <<< len: 2 main <<< str ==>2<== main <<< str ==>1<== main <<< x: [2] main <<< x: [1] main <<< graph: 2 1 main <<< clone: 2 1
We are provided with an adjacency list for the nodes starting with node 1 and moving in monotonically ascending order. In the first test case, we have four nodes with values 1, 2, 3, and 4. The associated adjacency list for each node is implied.
Our test code seems to read and parse the input line. It determines the number of nodes in the graph and displays such information as len. The strings associated with each adjacency list are then displayed. It seems that we extract the integer values and display them as part of a data structure. This will become clear when we look at the test code.
It seems that the initial graph is displayed. Our test code displays the adjacent nodes for each node. The edges do match the input.
It then seems that we make a clone (deep copy) of the graph and display it. Since the graphs match we have some confidence that the solution works.
Please note that the links are not displayed in any specific order. If required, we could have displayed them in ascending order.
/**
* Test scaffolding
*
* !!!! NOT PART OF THE SOLUTION !!!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** ****
ArrayList<Integer[]> al = null;
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read adjacency list ****
String[] strArr = br.readLine().trim().split("],\\[");
// **** close the buffered reader ****
br.close();
// **** get the length of the String[] ****
int len = strArr.length;
// ???? ????
System.out.println("main <<< len: " + len);
// **** ****
if (len == 1 && strArr[0].equals("[]")) {
al = new ArrayList<>();
} else if (len == 1) {
al = null;
} else {
// **** remove [ and ] from first and last entries ****
strArr[0] = strArr[0].substring(1);
strArr[len - 1] = strArr[len - 1].substring(0, len - 1);
// ???? ????
for (String str : strArr)
System.out.println("main <<< str ==>" + str + "<==");
// **** convert array of string to list of Integer[] ****
al = new ArrayList<>();
// **** populate the array list ****
for (String str : strArr) {
// **** convert String to int[] ****
int[] tmp = Arrays.stream(str.split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** convert int[] yp Integer[] ****
Integer[] arr = IntStream.of(tmp)
.boxed()
.toArray(Integer[]::new);
// **** add Integer[] to list ****
al.add(arr);
}
}
// ???? ????
// if (al != null)
// al.forEach( x -> System.out.println("main <<< x: " + Arrays.toString(x)) );
// **** populate initial graph ****
Node graph = populateGraph(al);
// ???? display initial graph ????
if (graph == null)
System.out.println("main <<< graph: null");
else {
System.out.print("main <<< graph: ");
displayGraph(graph, al);
}
// **** clone the graph (method of interest) ****
Node clone = cloneGraph(graph);
// ???? display cloned graph ????
if (graph == null)
System.out.println("main <<< clone: null");
else {
System.out.print("main <<< clone: ");
displayGraph(clone, al);
}
}
Our test code should read the input line holding the adjacency list. The data should be properly packaged for the method that generates the graph. We then need to call the method in question which should return the cloned graph. In addition we display the initial and the cloned graph.
Please look at the code. I believe we should be able to follow it without issues.
/**
* Populate initial graph.
*
* !!!! NOT PART OF SOLUTION !!!!
*/
static Node populateGraph(List<Integer[]> al) {
// **** sanity checks ****
if (al == null)
return null;
if (al.size() == 0)
return new Node(1);
// **** initialization ****
HashMap<Integer,Node> hm = new HashMap<>();
// **** get root neighbor values ****
Integer[] arr = al.get(0);
// **** create and populate node neighbors ****
ArrayList<Node> neighbors = new ArrayList<Node>();
for (int j = 0; j < arr.length; j++) {
Node n = new Node(arr[j]);
neighbors.add(n);
hm.put(arr[j], n);
}
// **** create root node ****
Node graph = new Node(1, neighbors);
// **** save node reference in map ****
hm.put(graph.val, graph);
// **** traverse the array list creating and connecting nodes for the graph ****
for (int i = 1; i < al.size(); i++) {
// **** get values for node neighbors ****
arr = al.get(i);
// **** check if the current node is in the graph ****
Node node = hm.get(i + 1);
// **** connect neighbors to this node ****
for (int j = 0; j < arr.length; j++) {
// **** look for node in the hash map ****
Node n = hm.get(arr[j]);
if (n == null) {
n = new Node(arr[j]);
hm.put(arr[j], n);
} else {
if (!n.neighbors.contains(node))
n.neighbors.add(node);
}
}
// **** add neighbors to this node ****
for (int j = 0; j < arr.length; j++) {
// **** ****
Node n = hm.get(arr[j]);
// **** ****
if (!node.neighbors.contains(n))
node.neighbors.add(n);
}
}
// **** return graph ****
return graph;
}
This method IS NOT PART OF THE SOLUTION. We use it to generate the input graph for our method in question.
We perform some sanity checks.
We then declare a hash map which we will use to keep track of nodes that we have created for the graph. We need to get references to them to connect the nodes.
We declare an array to hold the adjacent node values. For each adjacent node we create the node and make a reference in our hash map. Note that the nodes are just floating in our hash map. We do not have a graph yet.
We create the node for the root node (value 1) using the neighbors we just created. At this point we have the root node pointing to the adjacent nodes but such nodes are not connected yet. We save the root node reference in the hash map.
We are now ready to move through the rest of the nodes which are in ascending order. Note that the loop is split in two parts. The first part handles connecting the adjacent nodes to the current node. The second part attaches the required nodes from the hash map to the graph.
When done we return the input graph.
/**
* Display graph.
*
* !!!! NOT PART OF SOLUTION !!!
*/
static void displayGraph(Node graph, ArrayList<Integer[]> al) {
// **** sanity checks ****
if (graph == null)
return;
// **** initialization ****
Node p = graph;
Node q = null;
// **** ****
for (int i = 0; i < al.size(); i++) {
// **** display neighbors for this node ****
for (int j = 0; j < p.neighbors.size(); j++) {
System.out.print(p.neighbors.get(j).val + " ");
if (p.neighbors.get(j).val == (i + 2))
q = p.neighbors.get(j);
}
// **** move to next node in the graph ****
p = q;
}
// **** ****
System.out.println();
}
We would like to see if the graph was properly built. This method provides us with the neighbors of each node we traverse.
The idea is to visit each node and display the neighbors. We could have done it without the need of the array list but since this method IS NOT PART OF THE SOLUTION I would leave that as a bonus point.
/**
* Return a deep copy (clone) of the graph.
* Entry point for recursive DFS method.
*
* Runtime: 25 ms, faster than 90.62% of Java online submissions.
* Memory Usage: 39 MB, less than 87.79% of Java online submissions.
*
* Time complexity: O(n) because we visit each node once.
* Space complexity: O(n) because we make a copy of each cloned node.
*/
static Node cloneGraph(Node node) {
// **** sanity check(s) ****
if (node == null)
return null;
// **** call recursive method (returns cloned graph) ****
return cloneGraph(node, new HashMap<>());
}
This is the method of interest. We will tackle the problem using a BFS traversal which is recursively implemented in the next code snippet.
Note that the hash map will be used to keep references to the nodes in a similar way we used it when creating the initial graph.
/**
* Recursive DFS method.
*/
static private Node cloneGraph(Node node, HashMap<Integer,Node> hm) {
// **** check if node is in hm (no need to visit this node) ****
if (hm.containsKey(node.val))
return hm.get(node.val);
// **** clone this node ****
Node clone = new Node(node.val);
// **** put cloned node in hm ****
hm.put(clone.val, clone);
// **** recursive call ****
node.neighbors.forEach( n -> clone.neighbors.add(cloneGraph(n, hm)));
// **** return cloned node (copy of graph) ****
return clone;
}
We need to visit each node in the clone graph once. If the node is not available, we then create it. Note that at that time we do not take into consideration adjacent nodes.
If we did not find the node in the hash map we create a cloned node with the specified value.
We put the cloned node in the hash map so we can refer to it by value in order to connect it to adjacent nodes.
For each neighbor in the node (not the clone yet) we make a recursive call. Note that the nodes are connected as needed.
When all is said and done the clone node is the deep copy of the first node.
Please make sure you single step through the code to make sure we are in agreement with the DFS code.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 7,252 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com