Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution
ฝัง
- เผยแพร่เมื่อ 4 ต.ค. 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: You are given a standard linked list with next pointer BUT each node carries an additional random pointer to any given node in the linked list. Clone the linked list.
Let us first see the mental barriers and problems that we face while solving this.
It is trivial to make a copy of the linked list nodes with only the next pointers, but the random pointer on each node presents a problem.
We will notice that we have trouble establishing the connection between the original linked list and the random pointers between nodes in the cloned linked list.
Approach 1 (Linear Space Solution)
Use a hashtable to facilitate the cloning.
Complexities
Time: O( n )
We will perform linear time traversals that keep our asymptotic behavior linear.
Space: O( n )
We will store a clone mapping for each node entailing linear space complexity with respect to the original list passed to us.
Approach 2 (Constant Space Solution)
Use the original list's node's next pointer to map to the clone list.
Complexities
Time: O( n )
We are still only doing linear time traversals
Space: O( 1 )
We do not store any auxiliary space that will scale as the input size gets arbitrarily large.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question on Leetcode: leetcode.com/p...
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.
where exactly is the code? I can't seem to see it
The repository is deprecated - we only maintain backtobackswe.com now.
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
Finally someone who likes to explain stuff and who does it enthusiastically. It's a pleasure to watch! !! Thanks ma dud! :)
great and sure
great stuff, I didn't even understand the question being asked on the leetcode page. Your diagram helped a ton, thank you.
sure
so far, that's my favorite video on BackToBackSWE channel, I smile everytime he says "again the code in the description" :)
haha yeah we transitioned to website
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.
haha
Ben's failure helped people like me, so thank you Ben, pls fail more haha!
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
U a beast
This is awesome! Clear explanation. Lost my job offer because of coronavirus and preparing for interviews.
Nice, contact us and we can give you a platform membership if you'd like
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!
If not for this video, I wouldn't have understood the question itself. Thank you so much for all your videos☺️
ye
A lot of questions I can't even understand what they're asking lol
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!
thx
WOW!! Without this problem, the Linked list are incomplete :) Thanks for whatever you taught us
sure
If i get this question for the first time, i would cry!!!
ye
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!!
I was asked this question in an interview today and I got it right just because of you!! Thanks man
which company bro?
great
lol chil
@@SumitKumar-fn3gj Pensando Systems
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 :)
got it thanks
Most detailed and effective teaching video I’ve ever seen on TH-cam, thank u, already get used to watching your video when eating, wish I could also someday read my offer from twitter too!
hahahahaha thank you. Food is very good.
Thanks Ben, you always make complex problems easier to understand! Shoutout from Canada!
hey
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
sure
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
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! =)
Thanks for all of your videos! Your video helped a lot. Got an offer from amazon!
👀👀👀 Will u be in Seattle this summer?
My number one preference is Seattle. I get my official offer Tuesday.
@@Rendbot ok
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.
This is far more clear than any tutorial I watched on youtube, please make more videos like this
ok
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.
thx
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 !
Perfect explanation bro ! Keep posting more videos !
ok, on it
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..
lol thx
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.
great and welcome
Second approach is just great 💥 u r a genius !
thanks!
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!
nice haha, I didn't come up with it either, just learned from someone else
@@BackToBackSWE Love your modesty here!
@@shruthib3366 it's tru
you are INCREADIBLE BEN.
nah
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!
You just made this really simple to understand! Thanks a ton!
sure
You're great at teaching, congratz. Keep going as long as you can
thx
Can't get a better explanation 🤯
BIG thumbs up!! Loved the way you teach!
thank you
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 👌
Your are One of the best teachers on youtube , i learn so much from you
I am but a man
Awesome video! It would be really helpful, if you could put code in either description or github.
thanks and the repository is deprecated - we only maintian backtobackswe.com's solutions.
This blew my mind lol
nice
Thank you for making it very simple to understand.
sure
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?
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.
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 .
Just came back the fourth time. Argh!!!!!!!!!!!!!
I wish! You did not deprecate the existing repository at least, even if you shifted things to backtobackswe.com. It was really helpful. :(
yes
Finally understood this. Thank you!
NO. FREAKING. WAY. WHAT. Wassup Cesare hahahahahaha
@@BackToBackSWE Haha back to the interview game and you come to my rescue
@@cesaredecal2230 lmao, good luck
Awesome explanation and beautiful way of rewiring nodes in the LinkedLists.
indeed
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.
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.
@@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?
You should've explained step-3 too i.e., restoring the 2 linked lists. It took me lot of time to understand that part. Other than that great video.
ok
@@BackToBackSWE Are you a frikin robot? How can you have time to reply to every single comment?
Never seen someone do that.
Exactly! @Ande, could you explain the restoring part or share the code associated with it
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.
It only took me first couple minutes to understand each solution, very good teaching.
ye
best explanation for this question out there
thanks
Awesome stuff dude
ye
Best Explanation Ever ! Thanks for all the great videos
sure
Great stuff. You said code is in the description. Where is it?
You ROCK bro, keep up the good work!
u rock
I have watched every single video of yours and loved it. My DS skills have definitely improved but
Can you please make a video on general web architecture (People know the basic like there is DNS then load balancer then web server etc..) but how these things work in real-time(like how DNS gets resolved, where does load balancer lies. what is web server, do we make one our own or do we use existing open course).
Please, Please make a 1-hour long video explaining every part from a practical point of view (no theoretical).
(Most of the time interview asks details of these things (also Http vs rest vs Webservices.. I have read a number of articles about them but didn't find any clear cut answer) and we get stuck because we have read the theory)
I am early waiting for your answer brother
Yeah sure haha
Really great explanation and thanks for providing the code!!
sure
Boss, could you please check the code page, it is not available, and as always thaaaanks for the great explanation 👍🏼👍🏼👍🏼
sure
found it from his github github.com/bephrem1/backtobackswe/blob/master/Linked%20Lists/CloneLinkedListWithRandomPointers/LinearSpace.java
You are an amazing teacher!
thx
Great Explanation!
Can't believe that I have watched this video and I still can't remember how to solve this problem.
haha
Great video thanks
sure
Very good explanation, thanks !
sure
Great and elegant explanation.
thanks
Why not just clone LL within the first pass with connections and iterate through both of the lists to restore the random pointers? Constant time access is great ofc, but I think there is a trade off between time complexity, space complexity and readability. The second one is quite tricky, why should I prefer it against the simplest one? Ofc it depends on the interviewer's thoughts:) Thank you for great explanation, anyway.
i agree, depends on what matters more to you/the interviewer
This is such an amazing explanation . Where is the link to the code?
The repository is deprecated, we only maintain backtobackswe.com now.
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 ?
Yes, that is correct, but we are not counting the output space
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!
sure and ik
What i think pre-watching the video:
Go trough the list, write down all the addresses of nodes. For each address, make new space in memory and write it down. Now go trough the list again. The data is stored at the address specified, and the pointers are run through it to find new values.
ye
You are an amazing teacher !!!!
thanks
This is beautiful and you are amazing.
ur cool
Just awesome as usual. Bravo!
thx
This is such a beautiful explanation!
I could not find the code in the description. Can someone help me?
The repository is deprecated - we only maintain backtobackswe.com now.
Thanks for posting Ben! Arif sira newu. Berta!
Thanks
good explanation
sure
Hey man, awesome explanation. Just a little hard to follow since the code is no longer available
thanks and yes, the repository is deprecated - we only maintain backtobackswe.com now.
Back To Back SWE by that do you mean the code is located on your website? Also thank you for the reply
Very Nice Explaination (Y) and the efforts you take to make yours viewer understand (Y)
thx
Bro always you are telling code is in the description.where is the code broo
I cant even seen for one vedio of yourss
The repository is deprecated - we only maintain backtobackswe.com now.
awesome. thank you
sure
Really great explication. Thank you!
sure
The O(1) space confused me, the first time I got this question, my answer is to use a hashmap, but when I saw O(1) space, i am afraid to say my answer. lol
yeah, I couldn't have gotten it
Best explanation of this question.
ye
Great, great, great!
thanks
Amazing solution. I liked it. Very easy to understand and implement. Thank you. :)
sure
great video! lots of thanks!
sure
I can`t find the link for the code in description ?
The repository is deprecated - we only maintain backtobackswe.com now.
Really amazing explanation!!!! Thanks!
Where do I find the code? I cannot find it.
thank you, you made it look so easyyyyyyy......
ye
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.
Link to code in the description is broken. Can you please look into that?
ik
Great video!
In your description you gave misspelled Tushar Roy as Tuschar Roy. ( or is that a programming joke cause of the data type "char" you know :3)
my b and lol ye
Just Wow! Thanks a lot!!
sure
Brilliant way!
ye
Thanks man, you are so helpful
sure
I like your videos. I understand the concepts well but for the code, I follow only C++. Can you provide the C++ versions of the same code for the videos too in the description?
I cannot because I don't know C++ proficiently and do not have the time. I'd love if you contributed some samples though, the repo is open for anyone to contribute.
great explanation sir
Just Want to huge you my friend. #StayHome
hello
Where is the code in your description? I can't seem to find it.
The repository is deprecated - we only maintain backtobackswe.com now.
Great stuff dude!!!!
thx