Clone Graph - Depth First Search - Leetcode 133 

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

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

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?

Hi did you land a job man ?

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?

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.

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.

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]

Remove #s in Comment

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.

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.

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

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.

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.

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

sahi kaha ekdum

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.