Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution
HTML-код
- Опубликовано: 10 окт 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
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!
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
great stuff, I didn't even understand the question being asked on the leetcode page. Your diagram helped a ton, thank you.
sure
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
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
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!
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 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!!
WOW!! Without this problem, the Linked list are incomplete :) Thanks for whatever you taught us
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
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
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
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
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! =)
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
If i get this question for the first time, i would cry!!!
ye
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
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 !
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
This is far more clear than any tutorial I watched on youtube, please make more videos like this
ok
Thanks Ben, you always make complex problems easier to understand! Shoutout from Canada!
hey
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!
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
Most detailed and effective teaching video I’ve ever seen on RUclips, 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.
you are INCREADIBLE BEN.
nah
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?
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
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.
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.
Can't get a better explanation 🤯
Perfect explanation bro ! Keep posting more videos !
ok, on it
Your are One of the best teachers on youtube , i learn so much from you
I am but a man
Where do I find the code? I cannot find it.
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!!!!!!!!!!!!!
Second approach is just great 💥 u r a genius !
thanks!
Thank you for making it very simple to understand.
sure
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 👌
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
I wish! You did not deprecate the existing repository at least, even if you shifted things to backtobackswe.com. It was really helpful. :(
yes
You just made this really simple to understand! Thanks a ton!
sure
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
I can`t find the link for the code in description ?
The repository is deprecated - we only maintain backtobackswe.com now.
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.
Great stuff. You said code is in the description. Where is it?
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
BIG thumbs up!! Loved the way you teach!
thank you
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
Very good explanation, thanks !
sure
You're great at teaching, congratz. Keep going as long as you can
thx
This is such a beautiful explanation!
This is such an amazing explanation . Where is the link to the code?
The repository is deprecated, we only maintain backtobackswe.com now.
Really amazing explanation!!!! Thanks!
Great and elegant explanation.
thanks
Link to code in the description is broken. Can you please look into that?
ik
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
You are an amazing teacher!
thx
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
I could not find the code in the description. Can someone help me?
The repository is deprecated - we only maintain backtobackswe.com now.
Best explanation of this question.
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.
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
Best Explanation Ever ! Thanks for all the great videos
sure
Awesome explanation and beautiful way of rewiring nodes in the LinkedLists.
indeed
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
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
Great Explanation!
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
Really great explanation and thanks for providing the code!!
sure
best explanation for this question out there
thanks
thank you, you made it look so easyyyyyyy......
ye
what if the node has duplicate values? Will the solution with mapping work?
Great video thanks
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.
You are an amazing teacher !!!!
thanks
You ROCK bro, keep up the good work!
u rock
Where is the code in your description? I can't seem to find it.
The repository is deprecated - we only maintain backtobackswe.com now.
Very Nice Explaination (Y) and the efforts you take to make yours viewer understand (Y)
thx
great detailed explanation. Thank you sir for your efforts.❤❤❤
Just Wow! Thanks a lot!!
sure
Awesome stuff dude
ye
good explanation
sure
great explanation sir
Thanks man, you are so helpful
sure
Thanks for posting Ben! Arif sira newu. Berta!
Thanks
Can't believe that I have watched this video and I still can't remember how to solve this problem.
haha
great video! lots of thanks!
sure
Just awesome as usual. Bravo!
thx
This is beautiful and you are amazing.
ur cool
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
awesome. thank you
sure
I am confused as how the second solution is constant space.
If I understand correctly, for every node we will create its copy, so for n nodes we will have n copies,
how will that be a constant space?
The output doesn't count towards the algorithm's intrinsic space consumption. It can count if you consider output space.
Just confused about the O(1) space complexity solution, why is this considered constant space when we always have to create n additional nodes (where n is the size of the original linked list)
Great videos btw 😁
We ignore the space the output lists uses. Internally, to the algorithm itself, O(1) space is used. Output can be included or excluded from space...it is a default to exclude it since it is not very important and always a default.
Back To Back SWE thanks!
Love it! Thank you
Thank You!!
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
F-man, brilliant sir!
I was asked something similar of constant space using a Tree at Google...
They are really asking impossible questions now for interviews at Google..
And absolutely Yes, at google they would ask this O(1) space question.. they did to me..
"They called to reject me in person after 3rd interview, to let me know my answers weren't "Google" enough"
:(
Oh well keep on studying.. but this definitely helps!
Thnx
yes
This blew my mind lol
nice
Amazing solution. I liked it. Very easy to understand and implement. Thank you. :)
sure
Thank you