Clone Graph - Depth First Search - Leetcode 133

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@voski4904]

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]

[@lewisw29]

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

[@JohnDoe-mr6mq]

This is how I've approached this task too, now came here to look if there's another solution in this video

[@sudamlasi2007]

thank you this helped!

[@benpurcell591]

This is what I did. Still O(n) right? And way easier to reason about for me personally

[@vitzal3691]

I did this too at first, then refined it to one loop, then saw this dfs solution.

[@VladimirTheAesthete]

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.

[@tofumakesvideos]

Python is a cheatcode for some leetcode questions! Like question 371 Sum of Two Integers.

[@danyeun01]

how would the compiler link each node on its own

[@amynguy]

@@danyeun01 it keeps track of circular references

[@arkamukherjee457]

A general coding advice, avoid naming a variable copy, as it can confuse the code reviewer about library copy functions.

[@shivangitomar5557]

Finally understood and coded it myself after the theory explanation! Thanks :)

[@dumdumbringgumgum2940]

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.

[@minhthinhhuynhle9103]

I'm gonna use a HashMap like pretty much every Graph Problems. Thank you :>

[@halahmilksheikh]

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

[@zachtheyek]

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).

[@itachid]

Hey, can you share the demo?

[@ivantishchenko4686]

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. 👏👍

[@halcyonramirez6469]

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

[@castorseasworth8423]

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]

[@youssefel-shabasy833]

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]

[@lajoskicsi6910]

It's intereting to mention the Main.Node object in leetcode implements the __hash__() dunder method.

[@ashutoshbind8068]

Super helpful! Solved the linked list cloning q too with the same approach of hashing the old refs to the new ones

[@allen724]

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?

[@NeetCode]

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.

[@allen724]

@@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?

[@Bra1nstormeR]

Thankyou for providing such detailed solution with explanation.

[@nikhildinesan5259]

😀😀....was stuck in this same question from few days...

[@DBagg-zz4ip]

I did BFS with a 101-long list (according to constraints) instead of hashmap+visited set.

[@irisi3308]

Great explanation! I have a quick question - how do you prevent the code from looping through the nodes seen?

[@salimzhulkhrni1610]

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.

[@ZVEKOfficial]

What is the point of this question ? Where do we use this in real life

[@symbol767]

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.

[@aaen9417]

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

[@satadhi]

Hi did you land a job man ?

[@1000timka]

@@satadhi LOL

[@draugno7]

You mean IF, since there is always one person as smart and as in practice as Neetcode to take that job from us :D I got a scholarship for gifted people at uni but still there's always that someone (an Asian who does it better :') ). And my local jobs pay half of the US salary at most

[@MP-ny3ep]

Very beautiful explanation. Thank you !

[@div9210]

Wowww, it was really simple explanation.

[@az.akkkttt]

so first we create copies and then we make connections, right? if we follow the dfs

[@tomarintomarin9520]

NeetCode is the best

[@krateskim4169]

Awesome explanation

[@whatisnextthen9836]

can we solve this problem using constant space ?

[@khandmo]

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.

[@chenhaibin2010]

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?

[@meowmaple]

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

[@zekonja90]

You are using HashMap to see if you already visited node, as well to see if node is copied.

[@dollyvishwakarma2]

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 :)

[@netraamrale3850]

What is time and space complexity?

[@madhumithakolkar_]

Great solution as always, It would however be better to add the check >> if not node : return None :)

[@yilmazbingol4838]

in dfs, we return `copy`. Is not it supposed to be the clone of first Node.

[@VarunMittal-viralmutant]

How is that the custom class could be added as dictionary keys ? Maybe classes on Leetcode have defined some __hash__() methods ?

[@NeetCode]

Yes in python they do

[@VarunMittal-viralmutant]

@@NeetCode Thanks for confirming that. But if I try to write same code on an IDE first, I'll have to do that myself.

[@ifeanyionyejekwe4584]

Space and time complexity?

[@yilmazbingol4838]

I think time complexity O(N*N) because inside for loop we are making recursive calls. space complexity is O(N)

[@dss963]

@@yilmazbingol4838 nope , ultimate time complexity is n

[@SM-si2ky]

i generally like graph problems but this one is a little unintuitive & confusing

[@giannizamora7247]

thank you for the explantion NC!

[@Whiteroca]

What are u working as, NeetCode? Thanks

[@triscuit5103]

Hey man - I heard he was a dentist, learning programming as a hobby.

[@Whiteroca]

@@triscuit5103 That's pretty cool

[@jesseli5038]

@@Whiteroca he works at google

[@Whiteroca]

@@jesseli5038 Oh alright thanks

[@studyaccount794]

@@triscuit5103 Hey everyone, welcome back. Let's fix some teeth today.

[@JLJConglomeration]

I thought Python keys have to be immutable? I'm confused how you're assigning mutable objects (Node objects) as keys

[@netraamrale3850]

Amazing as always...!! Thanks for all the free content...!!!

[@yunyihuang9476]

could someone explain line 20 for me? How does it save all the neighbors' copy into the current node's list?

[@pahulhallan563]

why can't i just traverse the old graph, and each node, create a new and add to the new empty graph?

[@chilly2171]

11:15 the function will always return the root node.

[@aalapjethwa6452]

simple solution: return deepcopy(node)

[@vaalarivan_p]

dne: 5:00

[@river.]

underrated

[@ployapinon6345]

Clever! thanks for your post :)

[@nytymedarktruths7765]

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)

[@realyangfan]

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!

[@yashsrivastava5128]

i get an error when i create map of Node,Node ,Has any has java solution similar to this logic

[@brecoldyls]

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?

[@jointcc2]

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.

[@hanif3661]

4 js langs, try to cache node.val not node itself.

[@hanif3661]

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; ```

[@hwang1607]

Why can’t you use a set instead of a map

[@madhavkwatra5888]

How can you come up with solutions so easily ? where i struggle alot. Graphs are super hard 😭

[@MTX1699]

This problem sounds more complicated than it actually is.

[@mehmetnadi8930]

mind blowing

[@VineetKrGupta]

Day -17 of being unemployed and preparing for an interview. I was laid off recently

[@farazahmed7]

This question should be marked easy

[@whattokeepbro.5915]

sahi kaha ekdum

[@AustinCS]

Nah, you're wrong.

[@youssefel-shabasy833]

BFS is much better for this problem

[@mightyprogrammer2899]

Somehow Leetcode has deleted this problem

[@cryptshar6759]

nice

[@timilehinbakare7263]

its slow because you used dfs

[@unitycatalog]

What if the node IDs are not unique

[@cmelch]

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.

[@K4RD050]

even if you used the actual values, the problem states that the values go from 1 - n (for simplicity)

[@dr.merlot1532]

若しかして。。。

[@RaksohOap]

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])

[@skylakefreak3665]

return copy.deepcopy(node)