Amazon Coding Interview Question - Clone Graph (LeetCode)

[@alexshay7969]

Hi Michael, I'm new to graph and your explanation is great to understand and a great DFS solution. Thank you!!

[@sunnilabeouf]

Great to see the whiteboarding and intuition behind the problem, would love to see more videos like these!

[@AlgosWithMichael]

Thank you, I plan to do alot more!

[@saurabhdhamnaskar1737]

You explained the entire concept so easily. I would have saved my time if your video came up on the top on KZbin. Thanks brother

[@anvithakaranam1033]

Love your content. the best explanation anyone could get. I wish you uploaded more frequently :)

[@AlgosWithMichael]

Yea, I will try to upload more. Full time job gets in the way of my upload schedule

[@vidyasindhudubey5807]

Thank you soo much brother, your detailed explanation helped me a lot. Your really explained it very well. loved your content.

[@AlgosWithMichael]

You are most welcome

[@lapujain]

Amazing problem solving skills. Keep up the good work dude. Liked, subscribed (cant miss another concept :P)

[@AlgosWithMichael]

Awesome, thank you!

[@RahulVerma-fz2jf]

Really good. Understood the question and solution really well.

[@AlgosWithMichael]

Glad to hear, thanks so much for watching!

[@Prashantkumar-pn6qq]

Very nice explanation. Simple and effective!

[@AlgosWithMichael]

Glad it was helpful!

[@pl5778]

This is excellent, love the way you explain and show so intuitively. Would love for you to actually go through the code with the example line by line to completely drive home the implementation. Cheers.

[@AlgosWithMichael]

That is a great critique, I can do that in future videos. Thank you!

[@ZhouHaibo]

Great video, clear diagram and explanation.

[@AlgosWithMichael]

Glad it was helpful!

[@Jan_Jan_]

Great explanation! 👍

[@EchoVids2u]

Best Explanation on KZbin

[@AlgosWithMichael]

Wow, thanks!

[@victorochoa2111]

AWESOME explanation. Thank you!

[@AlgosWithMichael]

You're very welcome!

[@stackdev-io]

great work, keep the good work up

[@AlgosWithMichael]

Thank you so much for watching!

[@surajkiranreddymothe686]

Could you please explain why time complexity is O(N)? "When we are working on a node, we are touching all it's neighbors once" We do the process in quotes for all nodes. So shouldn't the time complexity be O(N*N)

[@AlgosWithMichael]

It is O(N) because when we touch each neighbor of a given node, we are saving that node inside of our map (think of the map as a cache), thus when we go to that node again we do not have to make a copy again after saving it.

[@surajkiranreddymothe686]

@@AlgosWithMichael Thanks, Michael. Now it makes sense. Basically, touching a neighbour which is already processed is O(1) operation. So it is O(N*1)=O(N).

[@raymondtan2795]

@@AlgosWithMichael Wait I still don't get it...even if touching a neighbor is a constant operation, couldn't we potentially be doing that E amount of times at each node, where E is the amount of edges in the graph? Like take a graph where every node is connected to every other node. Even when we get to the very last node where all of the new nodes have been created, don't we still have to loop through E amount of times? This would make the time complexity (E * V) (where V is the number of vertices in the graph), right?

[@tarlanabdullayev8980]

@@raymondtan2795 That makes sense. I have been thinking about that. it seems like it should be O(V * (V-1)) => O(V^2)

[@mettudheeraj1393]

can u give me the recursion tree for the code as i have hard time understanding the above recursion?

[@AlgosWithMichael]

If you look up any DFS animation online, that would be the equivalent (since this problem is just doing DFS).

[@mettudheeraj1393]

@@AlgosWithMichael thanks mate

[@AlgosWithMichael]

Anytime!

[@thecheekychinaman6713]

you're one of the few people working on graphs, and using a whiteboard. well appreciated and subbed. However, how does the code ensure that we always return the value 1 entry node?

[@AlgosWithMichael]

Glad you enjoyed it, more to come! The reason we always return the value 1 node is because we start recursion off by passing in the initial value 1 node every time. In the description, it notes that node 1 will always be our input node to the function.

[@supremoluminary]

What is the data in the test data? You wrote your tutorial but how does that translate to e.g. Input: adjList = [[2,4],[1,3],[2,4],[1,3]]? If you could explain that, I might get it. My interpretation of that data is four rows, two columns. but that's not right. It doesn't match your diagrams of bubbles connected by lines. I don't get it. What is this array of arrays test data?

[@AlgosWithMichael]

The index of the arrays are the connections. So for example, [[2, 4]] has only the 0 index. So 2 connections being 0 -> 2 and 0 -> 4.

[@numseidizer]

And the index (index + 1) is the val attribute.

[@MeetManga]

Is the time complexity wrong? should be O(V+E) ?

[@youmadvids]

great description

[@AlgosWithMichael]

Thanks!

[@bharathkalyans]

Loved it 🙌

[@AlgosWithMichael]

Thank you!

[@code7434]

Hi , please cover cherry pickup leetcode , u will love the que after reading

[@AlgosWithMichael]

I'll check it out!

[@NareshKumar-dw9xp]

I think it will not work when there is are self loops in the graph. Better to use Map instead of Map . Leetcode will accept your answer but Interview Bit will not :)

[@AlgosWithMichael]

Very true, good point. Thanks for watching and commenting!

[@NareshKumar-dw9xp]

@@AlgosWithMichael always welcome sir 💫❣️

[@azfa3605]

Time Complexity should be O(V + E)

[@EDROCKSWOO]

I think the ArrayList that you marked 2nd part dosen't actually enter until the recursion is finished. It is kind of confusing that you add the 2nd part after you create the map deeper search map. The arraylist map happens as the graph is finishing it's traversal and returns the "root". Overall still the best vid on youtube.

[@AlgosWithMichael]

Good feedback, I appreciate it. And thank you, I try haha

[@rohitranjan2767]

what to do in case of duplicate value nodes?

[@AlgosWithMichael]

For this problem, we can always assume the node values will be unique.

[@AD-fs6hr]

Nice Video. Suggestions : Can reduce video length, dont use language specific keywords.

[@AlgosWithMichael]

Yea, good points. I try my best to reduce the length of the videos, but they always seem to be longer than expected. Thanks for watching!

[@testingDhippiuh]

Thanks for sharing

[@AlgosWithMichael]

Thanks for watching!

[@shaileshhegde9205]

So the map is basically used for memoization

[@AlgosWithMichael]

Yea, pretty much!

[@shaileshhegde9205]

Michael Muinos this is helping me a lot!I just cleared my online assessment with amazon sde 1,hopefully will land a direct onsite ,your problems are nevertheless helping me,thank you :)

[@AlgosWithMichael]

That is awesome, I hope it worked out for you!

[@jagrit07]

Thanks for video, What does 1 prime 2 prime means ?

[@AlgosWithMichael]

It's more of just a way to denote the original and cloned. Thanks for watching!

[@dineshteja8092]

bro,can u make a vide on bipartite graph ?

[@AlgosWithMichael]

Yea, I'll add it to the list

[@rahuldabas8233]

you gained a sub.....: )

[@AlgosWithMichael]

Sick, thanks!

[@in_tyler_we_trust]

🧠💀