Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution

[@BackToBackSWE]

Table of Contents: Me Talking 0:00 - 0:32 The Problem Introduction 0:32 - 1:43 Assessing What We Know 1:43 - 1:59 Finding Our Mental Barriers 1:59 - 4:09 The Hashtable Breakthrough 4:09 - 4:47 Linear Space Solution Walkthrough 4:47 - 9:33 Can We Do Better? :) 9:33 - 10:55 Constant Space Solution Walkthrough 10:55 - 16:46 Wrap Up 16:46 - 17:19 The code for this question is in the description. Both the linear space and constant space solutions are addressed.

[@JT-yn4zk]

where exactly is the code? I can't seem to see it

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@rishabkumar4940]

I just got placed in Amazon and I want to extend my deepest thanks to you. You helped me a lot man!! Thank you and all the best for your amazing channel

[@dirkneuhauser8213]

Finally someone who likes to explain stuff and who does it enthusiastically. It's a pleasure to watch! !! Thanks ma dud! :)

[@BackToBackSWE]

great and sure

[@paul-mw6pc]

great stuff, I didn't even understand the question being asked on the leetcode page. Your diagram helped a ton, thank you.

[@BackToBackSWE]

sure

[@MultiPriya28]

You are the first teacher who has made me fall in love with DS.. I never thought I would ever dare to solve such kinda problems.. :D I started with quick sort and here I am.. Great explaination! And to all the followers : Just watch the video in fast forward mode.. !!!! ;D

[@BackToBackSWE]

U a beast

[@yanxichen4236]

Well, I for one am glad you failed this question for that interview then... am I allowed to say that? lol Great video as always.

[@BackToBackSWE]

haha

[@batman_1st]

Ben's failure helped people like me, so thank you Ben, pls fail more haha!

[@MiddleEasternInAmerica]

so far, that's my favorite video on BackToBackSWE channel, I smile everytime he says "again the code in the description" :)

[@BackToBackSWE]

haha yeah we transitioned to website

[@cryptojeff3993]

This is awesome! Clear explanation. Lost my job offer because of coronavirus and preparing for interviews.

[@BackToBackSWE]

Nice, contact us and we can give you a platform membership if you'd like

[@tapasyak429]

I just found your channel and hands down this is THE BEST in terms of teaching how to solve a coding problem. Most of the videos I see just have the answer in hand and they try to explain how that answer works. But nobody tries to tell you how to come up with that answer ourselves first with common sense. This video exactly has what other's are lacking. On top of that, see that enthusiasm in that guy. I love him!

[@vishnuvardhan623]

When I first saw the question,I thought it was just similar to clone graph and other thing is we should not mess up with original linked list pointers.But messing up with original linked list pointers gave the constant space solution😱.Awesome explaination!

[@BackToBackSWE]

thx

[@lugiadark21]

When I first read the question I was like WTF I cannot solve this, after seeing your video I was able to code it without looking at the code. Thanks again!! Your videos are the best!!

[@sanjanachopra2100]

If not for this video, I wouldn't have understood the question itself. Thank you so much for all your videos☺️

[@BackToBackSWE]

ye

[@seungjinkim8860]

A lot of questions I can't even understand what they're asking lol

[@RitikSharma-pc5yj]

WOW!! Without this problem, the Linked list are incomplete :) Thanks for whatever you taught us

[@BackToBackSWE]

sure

[@osamaxz5720]

you are one of the best teachers, I solved it in O(n^2) and I don't watch your videos to see the solution as I really watch to see how to think, my thinking was near to yours but surly your is better and helped me a lot of learning how to think in more efficient way, thanks

[@rishabkumar4940]

I was asked this question in an interview today and I got it right just because of you!! Thanks man

[@SumitKumar-fn3gj]

which company bro?

[@BackToBackSWE]

great

[@BackToBackSWE]

lol chil

[@rishabkumar4940]

@@SumitKumar-fn3gj Pensando Systems

[@remykhayat5763]

i spent hours trying to do this and even tho the constant space answer is non-trivial you made it very easy to understand, thank you sooo much, i hope i see this question in my next interview

[@BackToBackSWE]

sure

[@amospan14]

Thank you for failing this interview question and instead of letting it define you as a failure, you used it as motivation to teach all of us. I appreciate it my man! =)

[@yvestuyishime5209]

If i get this question for the first time, i would cry!!!

[@BackToBackSWE]

ye

[@CrazyHunk14]

to be really honest i just got stuck with the same problem in my interview. where i was about to discover the constant space solutions but i could not(interview pressure) then i came back to your channel and found out you too. now i am felling well about myself. still i am gonna binge all your videos thanks for helping you are doing a great job.

[@BackToBackSWE]

thx

[@ovoboyz1521]

Thanks Ben, you always make complex problems easier to understand! Shoutout from Canada!

[@BackToBackSWE]

hey

[@mvm9888]

Most detailed and effective teaching video I’ve ever seen on KZbin, thank u, already get used to watching your video when eating, wish I could also someday read my offer from twitter too!

[@BackToBackSWE]

hahahahaha thank you. Food is very good.

[@kuralamuthankathirvelan]

Perfect explanation bro ! Keep posting more videos !

[@BackToBackSWE]

ok, on it

[@Rendbot]

Thanks for all of your videos! Your video helped a lot. Got an offer from amazon!

[@BackToBackSWE]

👀👀👀 Will u be in Seattle this summer?

[@Rendbot]

My number one preference is Seattle. I get my official offer Tuesday.

[@BackToBackSWE]

@@Rendbot ok

[@Paradise-kv7fn]

from where did you prepare and how? I have just finished college and will be joining a tier 2 product based company but am planning to switch to the big 4 in the next year or so.

[@tonybernoulli7859]

This is far more clear than any tutorial I watched on youtube, please make more videos like this

[@BackToBackSWE]

ok

[@wishfulthinker6139]

Explanation was soo good that i didn't even had to watch the code and was able to code it in one go...i subscribed at lightspeed.

[@BackToBackSWE]

great and welcome

[@Uniyaltech]

you are INCREADIBLE BEN.

[@BackToBackSWE]

nah

[@chengjiang7051]

I have thought about a few minutes for the solution of constant space but in vain. When i saw you set the origin node's next pointer to the mirror node , I suddenly got the key point. hahaha Genius! Thx!

[@BackToBackSWE]

nice haha, I didn't come up with it either, just learned from someone else

[@shruthib3366]

@@BackToBackSWE Love your modesty here!

[@BackToBackSWE]

@@shruthib3366 it's tru

[@waxylayer8353]

Second approach is just great 💥 u r a genius !

[@BackToBackSWE]

thanks!

[@r1jsheth]

BIG thumbs up!! Loved the way you teach!

[@BackToBackSWE]

thank you

[@rajatverma1688]

Not only I like the way he explains , i love the extra bit of fun he adds to the videos like *door opens ey* mixing tuschar roy videos in between .. fun content ben..

[@BackToBackSWE]

lol thx

[@darshandani1]

Extremely well-explained ! Thank you for walking us over through the entire thought process. I had this question in an interview too and I failed to see all the small issues that you told in the video. Thanks !

[@zihaoyan4741]

This is way more intuitive than most sol on lc. Their algo makes sense but hard to implement when coding for me. your solution is much straight forward and I could come up with exact same answers just after viewing your video!

[@dochaar]

Yet another amazing video Ben! This video might help so many other folks to get across the line at Google, can't thank you enough. Also, quick note, the url to the code doesn't work and seems to have updated since you added two new files into your GIT repo (constant space and linear space). Please update the links so it might help folks going forward :)

[@BackToBackSWE]

got it thanks

[@fannnatic]

awesome. thank you

[@BackToBackSWE]

sure

[@arbazshaikh4447]

I can`t find the link for the code in description ?

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@alitherland765]

Where do I find the code? I cannot find it.

[@heyjoe5920]

Man, thank you so much. Great explanation, especially of O(1) space solution.

[@gamberril]

Very good explanation, thanks !

[@BackToBackSWE]

sure

[@kaustubhdwivedi1729]

Can't get a better explanation 🤯

[@gulshansingh3933]

Awesome stuff dude

[@BackToBackSWE]

ye

[@meenameiss]

You're great at teaching, congratz. Keep going as long as you can

[@BackToBackSWE]

thx

[@SuprBrian64]

Great Explanation!

[@ankurgupta4696]

Your are One of the best teachers on youtube , i learn so much from you

[@BackToBackSWE]

I am but a man

[@SarabjotSingh294]

Really amazing explanation!!!! Thanks!

[@mohitbhatia1994h]

Great and elegant explanation.

[@BackToBackSWE]

thanks

[@ogetysaivamsi106]

Thank you for making it very simple to understand.

[@BackToBackSWE]

sure

[@kunqian06]

Just awesome as usual. Bravo!

[@BackToBackSWE]

thx

[@Anveshana837]

Great video thanks

[@BackToBackSWE]

sure

[@mrivesingh]

You just made this really simple to understand! Thanks a ton!

[@BackToBackSWE]

sure

[@ciarlok7778]

Great explanation

[@alexanderchao5389]

This is such a beautiful explanation!

[@prithazz]

You are an amazing teacher!

[@BackToBackSWE]

thx

[@shivanshrawat2688]

Brilliant explanation. I have a small question if we are creating copies of N nodes how is this constant space?(the second approach) We have to create N more Nodes everytime, pardon me but i am a little confused.

[@BackToBackSWE]

We often leave the space of the copied list out and only attest to the space allocation of the algorithm asymptotically (since the copy space usage is trivially understood). Either is common.

[@shivanshrawat2688]

@@BackToBackSWE So if create another list with N nodes or create N copies of all the nodes it wont increase space complexity? Space complexity will only increase if we use another data structure and add n items to it like a hash table or array or Map?

[@cesare-o7l]

Finally understood this. Thank you!

[@BackToBackSWE]

NO. FREAKING. WAY. WHAT. Wassup Cesare hahahahahaha

[@cesare-o7l]

@@BackToBackSWE Haha back to the interview game and you come to my rescue

[@BackToBackSWE]

@@cesare-o7l lmao, good luck

[@Alex-wy2ko]

great video! lots of thanks!

[@BackToBackSWE]

sure

[@scodz2007]

You ROCK bro, keep up the good work!

[@BackToBackSWE]

u rock

[@tapasu7514]

Best Explanation Ever ! Thanks for all the great videos

[@BackToBackSWE]

sure

[@Metachief_X]

Great stuff dude!!!!

[@BackToBackSWE]

thx

[@abhishekkumarjaiswal1507]

great explanation sir

[@vivekgr3001]

good explanation

[@BackToBackSWE]

sure

[@subhangijena4381]

Best explanation of this question.

[@BackToBackSWE]

ye

[@sukritkapil2562]

Just Wow! Thanks a lot!!

[@BackToBackSWE]

sure

[@veeralsharma6748]

best explanation for this question out there

[@BackToBackSWE]

thanks

[@tewodroswolde9830]

Thanks for posting Ben! Arif sira newu. Berta!

[@BackToBackSWE]

Thanks

[@Max-zf5ot]

You are an amazing teacher !!!!

[@BackToBackSWE]

thanks

[@KevinJohnMulligan]

From 5:51 you did a kind of stop frame animation thing with the video editing which was super satisfying to watch and the narration mapped perfectly too 👌

[@CHIRANJIBNANDY1]

I am little confused. Might be very trivial and a silly question to ask. Does not the constant space mean extra spaces/nodes we create in memory ? If that's the case we created / cloned all the nodes in the first pass of our constant space solution. Please correct me, what am I missing ?

[@BackToBackSWE]

Yes, that is correct, but we are not counting the output space

[@ankababuyou]

Link to code in the description is broken. Can you please look into that?

[@BackToBackSWE]

ik

[@cunghocthuattoan7869]

I could not find the code in the description. Can someone help me?

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@davidj2597]

Thanks man, you are so helpful

[@BackToBackSWE]

sure

[@shwetasharma-hz3ib]

thank you, you made it look so easyyyyyyy......

[@BackToBackSWE]

ye

[@shravyaramesh6040]

This is beautiful and you are amazing.

[@BackToBackSWE]

ur cool

[@mahadreamz]

Great stuff. You said code is in the description. Where is it?

[@gurleenkaur5786]

Really great explanation and thanks for providing the code!!

[@BackToBackSWE]

sure

[@kaustubhchaturvedi658]

why is space complexity O(1) for the 2nd approach? We are declaring n new node containers for n existing nodes. So the auxiliary space will scale up as input size increases.

[@indranilthakur3605]

Where is the code in your description? I can't seem to find it.

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@j.c9858]

Thank you for helping me out, it is the problem failed me in the most recent interview...could you please share the code again? seems the shared link has expired...appreciate!

[@BackToBackSWE]

sure and ik

[@priyankareddy7408]

Love it! Thank you

[@BackToBackSWE]

Thank You!! Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)

[@goodwish1543]

Wonderful. Good illustration, easy to understand. I found the solution similar to clone graph. And learned O(1) space solution, as you said, just for knowing it exists.

[@goodwish1543]

It only took me first couple minutes to understand each solution, very good teaching.

[@BackToBackSWE]

ye

[@xinyuyou7512]

Really great explication. Thank you!

[@BackToBackSWE]

sure

[@priyankmungra29]

great detailed explanation. Thank you sir for your efforts.❤❤❤

[@illiakailli]

thanks for a nice explanation! I can definitely see an improvement over the hashtable version. The only thing that’s not clear is why last solution is ‘constant space’, when you had to create N clones in addition to the original array?

[@Tasarran]

That's the product that is being asked for, it is understood that at least that much space will be taken up. What he means is that it doesn't create any EXTRA space that would have to be garbage collected in some way.

[@AmeyaKherodkar]

Very Nice Explaination (Y) and the efforts you take to make yours viewer understand (Y)

[@BackToBackSWE]

thx

[@uyennguyen-tw6kp]

thanks for your videos!!

[@BackToBackSWE]

sure

[@svdfxd]

Awesome explanation and beautiful way of rewiring nodes in the LinkedLists.

[@BackToBackSWE]

indeed

[@AbhishekSingh-fc6tb]

Brilliant way!

[@BackToBackSWE]

ye

[@snehalahire1194]

This is such an amazing explanation . Where is the link to the code?

[@BackToBackSWE]

The repository is deprecated, we only maintain backtobackswe.com now.

[@mohinim.1654]

Awesome video! It would be really helpful, if you could put code in either description or github.

[@BackToBackSWE]

thanks and the repository is deprecated - we only maintian backtobackswe.com's solutions.

[@ankugupta413]

This was so cool! Thanks

[@BackToBackSWE]

thanks

[@FirefoxGuy18]

Thank you

[@alperozdamar517]

Amazing solution. I liked it. Very easy to understand and implement. Thank you. :)

[@BackToBackSWE]

sure

[@dustinv9193]

Subscribed. love you man :)

[@BackToBackSWE]

love you too

[@gokuljegan5120]

Where the link for code in description?

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@savar33]

You are the man!

[@BackToBackSWE]

no u

[@steelcube]

Thanks for this!

[@BackToBackSWE]

yeah sure

[@agamdeepsingh1675]

what if the node has duplicate values? Will the solution with mapping work?

[@MithleshKumar-iz1dz]

Great, great, great!

[@BackToBackSWE]

thanks

[@cristianouzumaki2455]

I have come here thrice for the same question, not because I didn't understand the question but because I keep forgetting this trick. Also his explanations are always very good .

[@cristianouzumaki2455]

Just came back the fourth time. Argh!!!!!!!!!!!!!

[@aayushsarna6017]

Not able to access the given github url for code.

[@BackToBackSWE]

I restructured the repo

[@DonTaldo]

Awesome contentt