Leetcode 133 | Clone Graph — Transcript

Let's start with an interesting problem that appears quite often in interviews. The question is given LeetCode 133 Clone Graph. The task in this question is to just make an exact copy of the graph. So let's understand the question and explore its intuition and dive deep into the solution step by step. Let me read the problem. The problem states that given a reference of a node in a connected undirected graph, this is an undirected graph, return a deep copy clone of the graph. Each node in the graph contains a value integer and a list of nodes as its neighbors. As the graph has its neighbors, the node has the value and the neighbors of it. Test case format for simplicity: each node's value is the same as the node index. For example, the first node value is equal to 1, the second node value is equal to 2, and so on. The graph is represented in the test case using an adjacency list. Okay, so that's what we have given. We have given a node and that node is connected to every other node, and this is a totally connected graph and each node has two things: the value and the list. Let us understand with given types of examples. There are a couple of examples given. As you can see, there is an example given as there is an original graph which is cloned to a second graph. You can't return the same graph. Okay, this is the instruction, and as the second graph, we have to return this type of graph, and in the third, we can't return that graph. You can see the input method adjacency of the graph. This is given as neighbors of the graph as values, totally the index, and here we have the relationships of that graph. Coming towards the constraint of the question, the number of nodes in the graph is in the range from 0 to 100, meaning the node is from 0 to 100. So we can have a time complexity of n squared. Let us understand the question. The question states it has a node. Okay, so let us understand how the node is formed in this graph. So in this graph, we have two things in a node: one is the value of the node, let us take it as one, and the other is the array of neighbors. It has the array of neighbors that store the reference of that node, not the exact value; it stores the reference exactly. We have another graph. So let us duplicate it and let me show it to you. We have this group. We can take another duplicate. Two duplicates we can take. Two duplicates we can take. Let me erase the values. So the value for this is three. The value for this is three, and the value for this is four. We can assign the references of the nodes as, let's say, it is a reference A, it is the reference B, and the third has the reference C, and the fourth has the reference D. As per the question, the one is connected to 2 and 4. So, we can insert the reference of 2 and 4 to A, 2 and 4 to A. The reference of two is B, and the reference of four is D. So, we have this, and two is connected to 1 and three. So the reference of one is A, and the reference of three is C. What about three? The three is connected to two and four. Two has B, and four has D. Now the D is connected to 1 and three. So one is having A, and three is having C. Let me just swap one and four for clear understanding of the question. Okay. Let us connect it from this. Connected like this. Like this. One is connected to four, and four is connected to three. This is the graph we have. Do you understand? All the things having their references like A, B, and C. So the thing we have to perform in this graph is to just change the references of every node and change the reference wherever the reference is written. So we need just a new graph as, let's say, we have this graph, we just have to let me change the reference. X, Y, Z, W. One is connected to 2 and 4. So two has Y, and four is having W. Two is connected to A and C. A means 1 and three. So X and Z, and B is connected to B and D. B and T. So here we will have Y and W. Four is connected to A and C, means X and Z. That's the thing we have to perform. All right, to do that, the first thing we should have in our mind is how to create a new reference. The new reference will be created by the thing like Node node takes new node. New reference is equal to new node. Here we can enter the old reference of the node. So we can have the old reference. Old reference. This will create a copy of the node. To store the copy of the node, we must require a hash set. So hash set will have two types of storing techniques. One is node, and another should be node. Let's create a hashmap. Hashmap of type node, and another will be type of node which is empty. All right. We have these types of things. The idea to solve this problem comes with an intuition. So let us move forward with the intuition of this problem. The intuition of this problem is to just transfer a node to its new reference and then transfer its neighbor to the new reference. It will require DFS. So as we transfer the A to X, then transfer, then go to the B and transfer its node also, go to its neighbor, transfer them also. So we are going depth to depth. It is the DFS. DFS requires depth every time. So we use DFS, we use hashmap, and we just use the node and make another node with the new reference. Let us do a dry run. Okay. So here we have value one. So we will take the first node as X. So we have X. Let it convert to another reference. Let us take it is converted as A. Now move to its neighbors as what its neighbors currently have. So currently its neighbors have Y and W. So we should move to the new neighbors, new neighbors. So convert the new neighbors to their new references. So take Y as when the first term we have converted, we can save it to our hashmap. So what our hashmap will have? Hashmap will have node of nodes. Okay. So for X, we have converted into A. So here we will mention the X is converted to A as old node, old node. It is new node. X is converted to A, and we have saved it to the hashmap. Now we move towards saving the neighbors. We will iterate to the neighbors and convert them to their new nodes. Pick up Y. Pick up Y and convert to their new node. So let me say Y is converted to B. Store this in the array. Y is converted to B. Now what are current of Y? What are current of Y? There is X and Z. To convert the X to its new node, we can first check if X is already converted or not. If X is already converted, we don't need to convert it again. So X has a new node reference as A. So just simply write it to convert for Z. To convert for Z, we should convert it to C. Okay. So let us save in the hashmap. So Z is converted to C. Now C, its current neighbors. What are current neighbors of C? Is Y and W. So what are new neighbors? New neighbors. First check Y is converted previously or not. So Y is converted, then replace it with its new reference. What about W? W is not converted. So let us convert W. W will be converted as D. So let us convert W as D and store it to the hashmap. All right. Now move to the current of W. Move to the current neighbors of W. The current neighbors of W is X and Z. So let's make it the new neighbors. So X is previously defined as A, and Z is also previously defined as C. So the function will end here. It will return to this as what is its new node is D. So we will mention the D here as W is converted to D, and also this C will return to this B. So we will write C. Now this B will return to this place. So Y is converted to B. And now we will check for W. Is W previously converted? Yes, W is previously converted. We can check it by the hashmap. So, replace it with D. All right. So, all things currently have their new node as this is having, this is also having, this is also having, and this is also having this new reference. So, this thing we must code it in a pseudocode. Let us first take how our pseudocode will work. The first thing in pseudocode is to check if the current node is already in map or not. If it is already in map, just take a return from it. If it is not in the map, you should create a new reference of it, store it in the map, and then traverse.

question and uh explore its intuition and dive deep to the solution step by step. Let me read the problem. The problem states that given a reference of a node in a connected undirected graph.

This is a undirected graph. Return a deep copy clone of the graph. Each node in the graph contains a value integer and a list of nodes as its neighbor. As the graph have its neighbor. So the node have the value and

the neighbors of it. Test case format for simplicity. Each node's value is same as the node index. For example, the first node value is equals to 1. The second node value is equals to two and so on. The graph is represented in the

test case using an adjacy list. Okay. So that's what we have given. We have given a node and that node is connected to every other nodes and uh this is a totally connected graph and each node have two things the value and the list.

Let us understand with given type of examples. There are a couple of examples given as you can see there is example given as there is original graph which is cloned to a second graph. You can't return the same graph. Okay, this is the

instructions and uh as second graph we have to return this type of graphs and in third we can't return that graph.

You can see the input method adjacency of the graph. This is given as neighbors of the graph as values is totally the index and here we have the relationships of that graph.

Coming towards the constraint of the question is the number of the node in the graph is in the range from 0 to 100 means the node is from 0 to 100. So we can have a time complexity of n².

Let us understand the question. The question states as it have a node. Okay. So let us understand how the node is formed in this graph. So in this graph we have two things in a node as one is the value

of node let us take it as one and other is the array of neighbors it have the array of neighbors store the reference of that node not the exact value it store the reference exactly we have another graph

So let us duplicate it and let me show it to you. We have this group.

We can take another duplicate. Two duplicates we can take. Two duplicates we can take. Let me erase the values.

So the value for this is three. The value for this is three and the value for this is four.

We can assign the references of the nodes as let's say it is a reference it is the reference b and uh the third have the reference c and fourth have the reference d.

As per the question, the one is connected to 2 and four. So, we can insert the reference of 2 and 4 to a 2 and 4 to A.

The reference of two is B and the reference of four is D. So, we have this and two is connected to 1 and three. So reference of one is A and the reference of three is C. What about three? The

three is connected to two and four. Two have B and four have D. Now the D is connected to 1 and three. So one is having A and three is having C. Let me just swap one and four for clear understanding of the

question. Okay. Let us connect it from this. Connected like this. Like this. One is connected to four and four is connected to three.

This is the graph we have. Do you understand? All the things having their references like A, B and C. So the thing we have to perform in this graph is to just change the references of every every node and change the

reference wherever the reference is written. So we need just a new graph as let's say we have this graph we just have to Let me change the reference.

X Y Z W One is connected to 2 and four. So two have Y and four is having W. 2 is connected to A and C. A means 1 and three. So X and Z and B is connected to

B and D. B and T. So here we will have Y and W. four is connected to A and C means X and Z that's the thing we have to perform all right to do that the first thing we

should have in our mind that how to create a new reference the new reference will be created by the thing like Node node takes new node. New reference is equals to new node.

Here we can enter the old reference of the node. So we can have the old reference.

Old reference. This will create a copy of the node. To store the copy of the node, we must require a hashet.

So het will have two types of storing techniques. One is node and another should be node.

Let's create a hashmap. hashmap of type node and another will be type of node which is empty.

All right. We have these type of things. The idea to solve this problem comes with an intuition. So let us move forward with the intuition of this problem. The intuition of this problem to just transfer a node to its new

reference and then transfer its neighbor to the new reference. It will require DFS. So as we transfer the A to X then transfer then go to the B and transfer its node also go to its neighbor transfer them also. So we are going

depth to depth. It is the DFS. DFS require depth every time. So we use DFS, we use hashmap and we just use the node and make another node with the new reference.

Let us do a dry run. Okay. So here we have value one. So we will take first node as X. So we have X. Let it convert to another reference. Let us take it is converted as A. Now move to

its neighbors as what its neighbors currently have. So currently it's neighbor have have y and w.

So we should move to the new neighbors new neighbors. So convert the new neighbors to their new references.

So take y as when the first term we have converted we can save it to our hashmap. So what our hashmap will have? Hashmap will have node of nodes.

Okay. So for x we have converted into a. So here we will mention the x is converted to a as old node. Old node it is new node X is converted to a A and we have saved it to the hashmap. Now we move towards

saving the neighbors. We will iterate to the neighbors and convert them to their new nodes.

Pick up Y. pick up y and convert to their new node. So let me say y is converted to v. store this in the array.

Y is converted to v. Now what are current of y? What are current of y? There is x and z.

To convert the X to its new node, we can first check as X is already converted or not.

If X is already converted, we don't need to convert it again. So X has a new node reference as A. So just simply write it to convert for J zed.

to convert for zed we should convert it to C. Okay. So let us save in the hashmap. So Z is converted to C. Now C its current neighbors. What are current neighbors of C is Y and W. So what are new neighbors?

New neighbors. First check Y is converted previously or not. So Y is converted then replace it with its new reference.

What about W? W is not converted. So let us convert W. W will be converted as D.

So let us convert W SD and store it to the hashmap. All right. Now move to the current of W.

Move to the current neighbors of W. The current neighbors of W is X and Z. So let's make it the new neighbors.

So X is previously defined as A and zed is also previously defined as C. So the function will end here. It will return to this as what is its new node is D. So we will mention the D here as W is

converted to D and also this C will return to this B. So we will write C.

Now this B will return to this place. So Y is converted to B. And now we will check for W. Is W previously converted?

Yes, W is previously converted. We can check it by the hashmap. So, replace it with D. All right. So, all things currently have their new node as this is having this is also having this is also having and this

is also having this new reference. So, this thing we must code it in a pseudo code.

Let us first take how our pseudo code will work. The first thing in pseudo code is to check as the current node is already in map or not. If it is already in map, just take a return from it. If it is not in

the map, you should create a new reference of it, store in the map and then traverse to its all neighbors with DFS approach.

So let us write a pseudo code of it. Powering off. Connect again soon. What will be the pseudo code?

Pseudo code of this. To write it pseudo code, we must have hashmap with us. Hashmap with us.

Hashmap of node and node which is MP. And we will call DFS from there.

The DFS will be called from the first node itself. DFS will be called from a node with this hashmap.

Okay. All right. We will create the DFS method. So there will be a node.

There will be the node n and the map. Node n and a map. First check if this node is null or not.

If it is null, return null. return nothing. Then also check is it previously existed in map dot contain.

We don't have to write the exact code in this. Now pass map DFS function. PFS function we will have simply we just simply check for the node as null or not. Check for null.

Check for null. Check for map exist or not. Map exist or not. map exist or not.

This thing will check out and return the node. Okay. After returning if it is not exist in the map, create new copy.

Create new copy. Save it to save it to map. Traverse to neighbors. Traverse to neighbor.

That's all in this question about pseudo codes. From pseudo codes, we need to convert it in actual code.

For that I will use intellig idea to convert this pseudo code to a actual code.

To convert is this to the actual code. The first we need a hashmap. Hashmap of nodes.

We will have hashmap of node as key also node as pairs. We will keep name it as map.

and we will call a function that will return the node. The function will be DFS. We will pass our first node and the map to that DFS function.

Let us create this DFS function. The DFS function is created. The first thing which will come in DFS function to check the note as check for check for null and check for existence.

Check for exist in map. Also make new copy. Change copy store to map traverse to traverse to neighbors.

To check null, we will have a if condition. If the node equal to null, it will return null.

Check for existence. If map dot contains key contains key node, it will return the value of that node. So map dot get of that node.

To make a new copy, we will create a object of node as uh new copy equal to new node and pass the older copy of it. node dot value store that copy to the map. So map dot put as the previous

node and the new copy of it. new copy of it to traverse to its neighbor.

We will use the older older nodes as node have two things the value and the neighbor. So older node will also have the neighbors.

Now we have neighbors of it. We have to find the every copy of the neighbors.

So node node new copy neighbor equal to dfs of uh the node and we will pass map to it. Now add this new copy of the neighbor to new copies neighbor.

New copy dot neighbor dot add that new copy neighbor. Now at last we just return a node of new copy.

That's the code. Let us run it. On execution we have seen that two two of the test cases are passed. We must paste it to lead code to check as it is passing all the test cases of lead code

or not. It just passed the three of test cases. Let me submit it. On submission, we just came to know that it passed all the 22 test cases too. Now let us talk about the time complexity of this question.

To know about the time complexity of this question, let me paste this question. Let us evaluate the time complexity of this question.

We made a neighbor. So we have a space complexity of big of n. Space complexity of big of n as due to hashmap of the question.

We used the stack space of big of n as we have we have to traverse all the nodes of the graph.

So we will have a stack space of n which will totally provide a space complexity as big of n.

To calculate the time complexity of this question time complexity of this question we have we first traverse all the nodes. So B vortex B vertexes we don't need any edges.

So big of v. So big go of n will be the time complexity of this question.

Also the time complexity to traverse all the edges. So bo of v + e as we are traversing to all the nodes and all other nodes linked to it. So linking of the node re represents the edges and all

other nodes represent the v. So v plus e we go of v + e is the time complexity of this dfs solution.

We also have the edge cases included in it as when the node will be null the recursion will return null.

And the summary of this question is we have to just think about the working of DFS. How the DFS is working and at the right time we applied the hashmap that make our question easy. So to cloning the graph we just need a

hashmap to store the nodes. Make the node as a new reference. traverse to all its neighbor, make them a new reference and restore it to the place of that new copy. It will automatically get converted. Thank you for watching.