A more brute force way to think about this problem. This is a good way to think about it before jumping into the solution given by NeetCode. #1. Use a hashmap to track originals to their clones (same as NC). #2. Traverse the original graph, visiting each node once, for each node just clone it's value without the neighbors. #3. Traverse the original graph again, visiting each node once, for each node find it''s clone and set the original's neighbors clones as the clone's neighbors. #4. return oldToNew[node]
First Clone(1) which Clones(2) and connects back to 1 (since it is already in the map) then Clones(3) which connects back to 2 and Clones(4) which connects back to 1 and 3. Now 4's neighbors are exhausted therefore 4 is returned to Clone(3) which returns 3 to Clone(2) which returns 2 to Clone(1). Only thing left from 1 is 4. Clone(4) now just returns 4 back to Clone(1) making the last connection.
Amazing, thank you for your explanation! You are doing a fantastic job. Please don't stop! This is how studying should be like! Education should be accessible to everyone. 👏👍
I made a stackblitz and the algorithm doesn't happen exactly you wrote. The recursive nature makes it hard to draw out but what I found was that the 1->2 and 1->3 are BOTH the last edges to be made. As the call stack unwinds is when the edges are created (for the most part). I have a demo if anyone's interested
I was wondering this too, but tbh I think it was more for the sake of explanation than accuracy; in reality, the algorithm presented visits each node, makes a copy, adds both to the hash map, then continues down the stack until it reaches the original node again, at which point it starts popping back up the stack, and then only does it add the edges (connections).
There is an alternative to recursive. Iterative BFS solution: class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return q, visited = deque([node]), set() clones = defaultdict(Node) while q: n = q.popleft() if n not in visited: clones[n].val = n.val for neighbor in n.neighbors: clones[neighbor].val = neighbor.val clones[n].neighbors.append(clones[neighbor]) q.extend(n.neighbors) visited.add(n) return clones[node]
if not node: return None clonedNode = { node: Node(node.val) } queue = deque([node]) while queue: curr = queue.popleft() for neighbor in curr.neighbors: if neighbor not in clonedNode: clonedNode[neighbor] = Node(neighbor.val) queue.append(neighbor) clonedNode[curr].neighbors.append(clonedNode[neighbor]) return clonedNode[node]
i have a much easier time understanding these than subarray problems.. I managed to solve this on my own. this is one was so much easier to me than the ones maxsubarray and subarray related problems. intution is simple. have a hashmap the key being the of the node val and the value being the node itself. if node val not in hashmap and node val and create a new node. traverse neighbors and check if neighbor value is in hashmap. if it is then just get it from the hashmap and don't recurse. the beauty of this is initially your node will not have neighbors in the hashmap but since you are storing references the references get updated. and in the end will give you the correct answer
Hi, thanks a lot for the video. May I ask at 1:38 why you commented that we use HashMap like every other graph problem? Sorry I am new to graph problems. Is Map a standard way to track the relationships of node to neighbours or something?
Yes, a common way of representing a graph is with an Adjacency List. It's usually implemented with a Hashmap because they are efficient. So for each nide, you map it to a list of it's neighbors.
That's the joke, we don't use 90% of this garbage in real life since we have prebuilt stuff on the job we will use. This is just mainly nonsense to pass the interview.
Hey @NeetCode, please come up with a playlist of videos that talk about the basic concepts of Python that come in handy for CP. P.S: really appreciate your videos! Kudos on such great content :)
preventing iteration through the same nodes that were seen already is handled by map. If a node is already seen, that means we would have already had a cloned node stored in the map. In that case, we just return the cloned node(already seen node) from the map and add it to its current cloned node's neighbor list. If we did not have the check, then we would have the case of infinite cycle.
Neetcode, have you considered a career in education and research? I feel as though you would be an excellent professor in algorithms and data structures, and would enjoy conducting research in algorithms. One of the difficulties of pursuing such a career path is that professors and researchers often have to seek out and apply for their own funding; however since you have a talent for articulating ideas and are clearly a self-motivated individual I think you would actually enjoy this aspect of it. Have you considered this?
I have a gut feeling he won't be interested. Leetcodes are designed for bridging the gap between what you learned in the academia and what you would actually use in a day to day job. In the academia it's mostly just Maths and it's also very hard to make it fun to learn.
thanks for the great explanation. I had thought to do DFS-backtrack, I need to remove the nodes that added to hashmap. Why it is not the case in this problem. How should I consider whether I need to remove a state from hashmap when I face a DFS-backtrack problem?
You don't need to do backtracking for this question as the first if statement already checks whether a node is already in the hasmap, and thus has already been visited, and returns if that is the case
Isn't your OldToNew in the wrong scope? The function is going to be called for each node, so you're not actually doing a Deep Clone as Node(1)'s neighbor Node(2) is not the same as Node(2), it's its own instance. Setting Node[1].neighbors[0].val = 22, will not affect Node[2].val. Basically you're creating n*n-1 objects instead of n because the OldToNew is in the function scope instead of a global scope (I know global is frowned upon, but Leet Code's validation system requires it in this specific instance)
version B: ``` if (!graph) return graph; function dfs (node) { if (node.copy === undefined) { node.copy = new Node(node.val); for (let n of node.neighbors) { node.copy.neighbors.push( dfs(n) ) } } return node.copy; } dfs(graph); return graph.copy; ```
It shouldn't matter. When we create the copy of the node we're just setting the value of the original as the value of the copy but the actual copy itself is a completely different unique object. Much of the same reason we are hashing the deep copy to the original they hold the same value but they are NOT the same node. So if two Nodes exist in the graph with the same value for example. We would create two different unique Node objects in memory that just happen to hold the same value. The actual objects in memory are different so when they exist in the hash they are represented as two unique items. When we look up an object in the hash we are comparing the object in memory and not the value the object holds.
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
A more brute force way to think about this problem. This is a good way to think about it before jumping into the solution given by NeetCode.
#1. Use a hashmap to track originals to their clones (same as NC).
#2. Traverse the original graph, visiting each node once, for each node just clone it's value without the neighbors.
#3. Traverse the original graph again, visiting each node once, for each node find it''s clone and set the original's neighbors clones as the clone's neighbors.
#4. return oldToNew[node]
This is more of a bfs thinking and is more straightforward. I began with this approach. Bit more code but easier to think about and understand
This is how I've approached this task too, now came here to look if there's another solution in this video
thank you this helped!
This is what I did. Still O(n) right? And way easier to reason about for me personally
Funny thing is that in Python all of this can be done with return copy.deepcopy(node). Your interviewer will probably not be impressed by that though.
Python is a cheatcode for some leetcode questions! Like question 371 Sum of Two Integers.
how would the compiler link each node on its own
A general coding advice, avoid naming a variable copy, as it can confuse the code reviewer about library copy functions.
Finally understood and coded it myself after the theory explanation! Thanks :)
First Clone(1) which Clones(2) and connects back to 1 (since it is already in the map) then Clones(3) which connects back to 2 and Clones(4) which connects back to 1 and 3. Now 4's neighbors are exhausted therefore 4 is returned to Clone(3) which returns 3 to Clone(2) which returns 2 to Clone(1). Only thing left from 1 is 4. Clone(4) now just returns 4 back to Clone(1) making the last connection.
I'm gonna use a HashMap like pretty much every Graph Problems. Thank you :>
Amazing, thank you for your explanation! You are doing a fantastic job. Please don't stop! This is how studying should be like! Education should be accessible to everyone. 👏👍
I made a stackblitz and the algorithm doesn't happen exactly you wrote. The recursive nature makes it hard to draw out but what I found was that the 1->2 and 1->3 are BOTH the last edges to be made. As the call stack unwinds is when the edges are created (for the most part). I have a demo if anyone's interested
I was wondering this too, but tbh I think it was more for the sake of explanation than accuracy; in reality, the algorithm presented visits each node, makes a copy, adds both to the hash map, then continues down the stack until it reaches the original node again, at which point it starts popping back up the stack, and then only does it add the edges (connections).
Hey, can you share the demo?
There is an alternative to recursive. Iterative BFS solution:
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node: return
q, visited = deque([node]), set()
clones = defaultdict(Node)
while q:
n = q.popleft()
if n not in visited:
clones[n].val = n.val
for neighbor in n.neighbors:
clones[neighbor].val = neighbor.val
clones[n].neighbors.append(clones[neighbor])
q.extend(n.neighbors)
visited.add(n)
return clones[node]
if not node:
return None
clonedNode = {
node: Node(node.val)
}
queue = deque([node])
while queue:
curr = queue.popleft()
for neighbor in curr.neighbors:
if neighbor not in clonedNode:
clonedNode[neighbor] = Node(neighbor.val)
queue.append(neighbor)
clonedNode[curr].neighbors.append(clonedNode[neighbor])
return clonedNode[node]
i have a much easier time understanding these than subarray problems..
I managed to solve this on my own. this is one was so much easier to me than the ones maxsubarray and subarray related problems.
intution is simple.
have a hashmap the key being the of the node val and the value being the node itself.
if node val not in hashmap and node val and create a new node.
traverse neighbors and check if neighbor value is in hashmap.
if it is then just get it from the hashmap and don't recurse.
the beauty of this is initially your node will not have neighbors in the hashmap but since you are storing references
the references get updated. and in the end will give you the correct answer
It's intereting to mention the Main.Node object in leetcode implements the __hash__() dunder method.
Hi, thanks a lot for the video. May I ask at 1:38 why you commented that we use HashMap like every other graph problem? Sorry I am new to graph problems. Is Map a standard way to track the relationships of node to neighbours or something?
Yes, a common way of representing a graph is with an Adjacency List. It's usually implemented with a Hashmap because they are efficient. So for each nide, you map it to a list of it's neighbors.
@@NeetCode Thanks bro. Ive learned a lot from your channel. Can you please do a video on Graph cycle detection / top sort using in degree?
At this point, even after I land a job, I will keep watching your videos just to enjoy the simplicity and elegance of your solutions
Hi did you land a job man ?
@@satadhi LOL
Super helpful! Solved the linked list cloning q too with the same approach of hashing the old refs to the new ones
Thankyou for providing such detailed solution with explanation.
What is the point of this question ? Where do we use this in real life
That's the joke, we don't use 90% of this garbage in real life since we have prebuilt stuff on the job we will use. This is just mainly nonsense to pass the interview.
Hey @NeetCode, please come up with a playlist of videos that talk about the basic concepts of Python that come in handy for CP.
P.S: really appreciate your videos! Kudos on such great content :)
I did BFS with a 101-long list (according to constraints) instead of hashmap+visited set.
😀😀....was stuck in this same question from few days...
Amazing as always...!! Thanks for all the free content...!!!
Very beautiful explanation. Thank you !
Great explanation! I have a quick question - how do you prevent the code from looping through the nodes seen?
preventing iteration through the same nodes that were seen already is handled by map. If a node is already seen, that means we would have already had a cloned node stored in the map. In that case, we just return the cloned node(already seen node) from the map and add it to its current cloned node's neighbor list. If we did not have the check, then we would have the case of infinite cycle.
Wowww, it was really simple explanation.
NeetCode is the best
Great solution as always, It would however be better to add the check >> if not node : return None :)
Neetcode, have you considered a career in education and research? I feel as though you would be an excellent professor in algorithms and data structures, and would enjoy conducting research in algorithms. One of the difficulties of pursuing such a career path is that professors and researchers often have to seek out and apply for their own funding; however since you have a talent for articulating ideas and are clearly a self-motivated individual I think you would actually enjoy this aspect of it. Have you considered this?
I have a gut feeling he won't be interested. Leetcodes are designed for bridging the gap between what you learned in the academia and what you would actually use in a day to day job. In the academia it's mostly just Maths and it's also very hard to make it fun to learn.
If every node is undirected can't that be created upon finding it as a neigbor? Then you would only need a set to contain the cloned nodes.
so first we create copies and then we make connections, right? if we follow the dfs
thanks for the great explanation. I had thought to do DFS-backtrack, I need to remove the nodes that added to hashmap. Why it is not the case in this problem. How should I consider whether I need to remove a state from hashmap when I face a DFS-backtrack problem?
You don't need to do backtracking for this question as the first if statement already checks whether a node is already in the hasmap, and thus has already been visited, and returns if that is the case
You are using HashMap to see if you already visited node, as well to see if node is copied.
could someone explain line 20 for me? How does it save all the neighbors' copy into the current node's list?
thank you for the explantion NC!
How is that the custom class could be added as dictionary keys ? Maybe classes on Leetcode have defined some __hash__() methods ?
Yes in python they do
@@NeetCode Thanks for confirming that. But if I try to write same code on an IDE first, I'll have to do that myself.
Awesome explanation
in dfs, we return `copy`. Is not it supposed to be the clone of first Node.
Can someone tell me what is the type 'Node' in python? why not just Node? Is it not the Single quotation marks String in python? Thanks!
Space and time complexity?
I think time complexity O(N*N) because inside for loop we are making recursive calls. space complexity is O(N)
@@yilmazbingol4838 nope , ultimate time complexity is n
I thought Python keys have to be immutable? I'm confused how you're assigning mutable objects (Node objects) as keys
Isn't your OldToNew in the wrong scope? The function is going to be called for each node, so you're not actually doing a Deep Clone as Node(1)'s neighbor Node(2) is not the same as Node(2), it's its own instance. Setting Node[1].neighbors[0].val = 22, will not affect Node[2].val.
Basically you're creating n*n-1 objects instead of n because the OldToNew is in the function scope instead of a global scope (I know global is frowned upon, but Leet Code's validation system requires it in this specific instance)
i generally like graph problems but this one is a little unintuitive & confusing
Clever! thanks for your post :)
i get an error when i create map of Node,Node ,Has any has java solution similar to this logic
How can you come up with solutions so easily ?
where i struggle alot.
Graphs are super hard 😭
11:15 the function will always return the root node.
What are u working as, NeetCode? Thanks
Hey man - I heard he was a dentist, learning programming as a hobby.
@@triscuit5103 That's pretty cool
@@Whiteroca he works at google
@@jesseli5038 Oh alright thanks
@@triscuit5103 Hey everyone, welcome back. Let's fix some teeth today.
What is time and space complexity?
Do you know how I can input it on and IDE, I realized Node is commented out on leetcode.
Remove #s in Comment
dne: 5:00
Somehow Leetcode has deleted this problem
simple solution: return deepcopy(node)
Day -17 of being unemployed and preparing for an interview. I was laid off recently
underrated
mind blowing
4 js langs, try to cache node.val not node itself.
version B:
```
if (!graph) return graph;
function dfs (node) {
if (node.copy === undefined) {
node.copy = new Node(node.val);
for (let n of node.neighbors) {
node.copy.neighbors.push( dfs(n) )
}
}
return node.copy;
}
dfs(graph);
return graph.copy;
```
This problem sounds more complicated than it actually is.
This question should be marked easy
sahi kaha ekdum
Why can’t you use a set instead of a map
nice
BFS is much better for this problem
its slow because you used dfs
若しかして。。。
What if the node IDs are not unique
It shouldn't matter. When we create the copy of the node we're just setting the value of the original as the value of the copy but the actual copy itself is a completely different unique object. Much of the same reason we are hashing the deep copy to the original they hold the same value but they are NOT the same node. So if two Nodes exist in the graph with the same value for example. We would create two different unique Node objects in memory that just happen to hold the same value. The actual objects in memory are different so when they exist in the hash they are represented as two unique items. When we look up an object in the hash we are comparing the object in memory and not the value the object holds.
I figure out an alternative recursive solution that for me is more intuitive.
hash_map = {node: Node(node.val)}
def dfs(current):
if current:
for n in current.neighbors:
if not n in hash_map:
hash_map[n] = Node(n.val)
dfs(n)
hash_map[current].neighbors.append(hash_map[n])