Copy List with Random Pointer - Linked List - Leetcode 138

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/copy-lin...
0:00 - Read the problem
5:07 - Coding Explanation
leetcode 138
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#sorted #array #python

[@aaen9417]

this time I figured out by myself that I would need 2 passes, 1 for the nodes creation and a second one for the linking, also I figured a hashmap would be the best way of accessing the copies. However, your solution is by far more simple and elegant. Thanks so much for inspiring us to keep practicing!

[@MrPaulzeng]

NeetCode gives the best Leetcode explanations on KZbin, imo

[@tnmyk_]

You were right, it's much easier to understand the solution by looking at the code than to explain it. Well done!

[@bernardpark3196]

Just wanted to say you are awesome, and thank you for your time and effort that you put into your videos! Much appreciated 🙏

[@Demo-man]

Your videos are great you have no idea how much you've helped me! For an alternative solution I also used a hashmap from nodes in the original list to nodes in the new list, but I was able to do this all in one pass! You can simply create the connections and create the new nodes as necessary, adding them to the hashmap. Then, if at any point when adding a connection for "next" or "random" you find that you've already created a node for the corresponding node in the original list then you can go ahead and use that pointer. Hope this helps someone!

[@sumitghewade2002]

I struggled with 3-4 Linked List questions from NeetCode list and watched and learnt from your videos. And finally was able to come up with the solution similar to yours without watching the video. Thank you. Your way of explaining algorithm is effortless. Please make a video on how to explain your thoughts about a question in an interview?

[@mrkandreev]

You have to know that exists second solution with O(1) space. It is possible if you change input linked list with appending clonned values between existed nodes in linked list.

[@ananya___1625]

I came up with very complicated solution and was amazed to see ur simple solution.Thanks a lot for your time and efforts

[@fredtrentini6791]

I solved the problem with some 10x more complicated logic using the id function to uniquely identify each node by it's memory address, and from there on making a hashmap that maps the memory address to the node, all because I had no idea you could assign an object as hashmap key... feels really nice to learn that but I am definitely feeling pretty stupid right now LOL

[@user-ib3ev5pl2t]

in c++ to use unordered map you'll need to create own hash function for non standard objects)))

[@rahulsbhatt]

I was complicating this by linking the new nodes except the random and decided to link the random ptr in the next pass, but your solution eases this out, thank you so much for posting this!

[@htoomyatnaing5775]

There is not a single Neetcode video that doesn't help me understand a problem. Much love and appreciation!

[@namanvohra8262]

Thanks! Was able to come up with the recursive approach pretty quickly after learning from your clone graph video!

[@kushagrabansal2107]

Please do more problems. I really love to watch your explanations after I give the problem a try.

[@GoziePO]

I really like this problem! Thanks for making these videos to help us all see the algorithms and thought process clearly!

[@sayanghosh6996]

this can be done in O(1) space by interleaving the old and new nodes while creating. def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return head ptr = head while ptr: newnode = Node(ptr.val, ptr.next) ptr.next = newnode ptr = newnode.next ptr = head while ptr: ptr.next.random = ptr.random.next if ptr.random else None ptr = ptr.next.next ptr = head.next while ptr: ptr.next = ptr.next.next if ptr.next else None ptr = ptr.next return head.next

[@user-mf8qt2by9i]

thanks man

[@tenkara101]

yup never figuring this out on my own lol

[@alexshay7969]

Thank you Fords!! I'm not well versed in Python, but when I looked at your Java code it's very clear.

[@symbol767]

Wow this is such a simple and amazing explanation, thank you, liked!

[@lovuitchen9332]

Clean, concise and good, as always! Thank you!

[@romangirin772]

It can be done via just _one_ traversal in recursive DFS manner class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': cloned = {} def dfs(node: 'Optional[Node]') -> 'Optional[Node]': if node is None: return None if node in cloned: return cloned[node] clone = Node(node.val) cloned[node] = clone clone . next = dfs(node.next) clone.random = dfs(node.random) return clone return dfs(head)

[@lewisw29]

genius

[@rockywu5502]

So simple and elegant, just wow.

[@aishwaryaranghar3385]

Thank You sir! Your explanations are the best!

[@danielrodrigues4903]

This can also be done with no extra space (besides what's needed for making the new list). It creates the nodes of the new list directly woven in-between the nodes of the original. Discovered I could do it in this way after using the Hint button on LeetCode. def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if head is None: return None ptr = head while ptr: new = Node(ptr.val, ptr.next) ptr.next = new ptr = ptr.next.next ptr = head while ptr: copy = ptr.next copy.random = ptr.random.next if ptr.random else None ptr = copy.next ptr = head.next while ptr: ptr.next = ptr.next.next if ptr.next else None ptr = ptr.next return head.next

[@ehsank7046]

Just ran to this question on leetcode today. Thanks for the video!

[@tien-yuhsin2095]

so when copying old nodes to copy, did you copy the references to next and random?

[@priyavardhanpatel6155]

damn bro you just killed it man..... really love your solutions. Thank you so much.

[@meghaldarji598]

I was scratching my head to figure out the solution for 20 mins. it's so hilarious that the solution could be something this simple! FML😂😂

[@eugenevedensky6071]

Cool approach. I added an index property to hash the nodes in Javascript, since attempting to hash with the node itself will lead to the key being "[object Object]" rather than the memory address as I imagine it does in python.

[@NeetCode]

That's a good idea!

[@AdemsPerspective]

You could also use Map in JS. It supports objects as key.

[@eugenevedensky6071]

@@AdemsPerspective nice suggestion, I’ve found it performs better than hash map, too.

[@ChaosB7ack]

If you're assigning an index you don't necessarily need to go through hashing btw, it might speed up things if you assign an array index instead and then create an array of nodes. This was my first intuition class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': curr = head if not curr: return None i = 0 while curr: curr.v = i i += 1 curr = curr.next curr = head res = [] for n in range(i): res.append(Node(0)) for n in range(i): res[n].next = res[n + 1] if n < i - 1 else None res[n].val = curr.val res[n].random = res[curr.random.v] if curr.random else None curr = curr.next return res[0] I don't love this because it relies on modifying the original and you usually don't really want to do that. Check out the weaving solution on leetcode, I think that one is the best one.

[@eugenevedensky6071]

@@ChaosB7ack Nice! I love getting responses to algo stuff like this way after I commented. Yeah, you're right, if you can reliably use an index it's as good as hashing basically.

[@wlcheng]

I come up with the same idea but your code is much more concise. Great content!

[@MP-ny3ep]

Superb Explanation !

[@chenhaibin2010]

that is the youtuber worth its name. Thank you

[@ManojBaruahadams]

Nice explanation with pass1 and pass2.

[@sachinkolachana6384]

Thanks. Would google expect a constant memory solution for an L5/L6 SDE role?

[@monarahmanimehr8365]

great explanation!!!

[@leul1407]

Thanks very helpful as always.

[@quirkyquester]

this is a fire video brother!

[@Matt-qr2xw]

You can use O(1) space for this problem. On pass one, build next links for the new list and establish a two way relationship with the matching node from the second list by using the unused random pointer of list2 to point to list 1. You can also break the next pointer on list1 and use it to point to the list2 node. Then on pass two use those pointers to get to the random node and build the random pointers.

[@glennquagmire9572]

By creating the deep copy you will automatically have O(n) space, otherwise it would not be a copy

[@LangePirate]

damn you're right XD@@glennquagmire9572

[@ap84wrk]

@@glennquagmire9572 the goal is to avoid extra space. Or let's say that all algorithms which must consider input as immutable have space complexity which is greater of equal to their output length.

[@glennquagmire9572]

@@ap84wrkWhat do you want tell me with that? If you have to create a copy you can never achieve constant space.

[@phantomhunter7985]

My mind just got blown. How was I not able to think of using a hashmap at all?

[@nachiket9857]

Same

[@yanxu9167]

very helpful, very clear! Thank you for sharing.

[@user-kz8ps1de3c]

Who would have thought this approach in thier first try? Not me..

[@Wanderor1]

Hey man! This was really helpful. Thank you so much!

[@bereketyisehak5584]

We can also do it in one pass by creating the copy of the random node as we go.

[@rohanpaul2504]

This is genious of a solution !!

[@vandananayak9426]

I just thanked god when I found yoursolution for this problem.

[@gauravsingh-re6yp]

Great explanation

[@santiagolimas2014]

Thank you!

[@jiajingxie7660]

Hello neetcode, I am a python beginner. I am learning LeetCode through your video explanation. I can say that you are the best and most detailed explanation I have ever encountered. I am currently studying in the United States (UC san diego). I can easily understand what you mean. Thanks for the video, hope you can make more videos. (Don't be lazy!)

[@NeetCode]

Thanks, and I'll definitely continue!

[@anyalauria1364]

brilliant as usual

[@aliciasuper7014]

Amazing explanation

[@NeetCode]

Happy it was helpful 🙂

[@Prohduct]

great explanation

[@dollyvishwakarma2]

The solution works for me only when I add additional checks if the key exists before accessing the oldToCopy which kind of makes sense to me since some node's random pointer could be None. Any thoughts?

[@frankl1]

Yeah right, this is why in the video he added the pair None:None in the hashMap.

[@zhe7518]

Is it possible to do it in one pass using a hashmap?

[@RAjat9590]

There is also one optimal solution to this which avoids the extra O(n) space of the hashmap.

[@LangePirate]

True by doing 3 passes instead of 2 you get time: O(3n), space: O(1) , which simplifies to time: O(n), space: O(1), which is technically better. Hint: use the random references wisely!

[@LangePirate]

actually someone pointed out that by creating a deep copy you're already at O(n) space... so rip XD

[@ranvirchhina5179]

@@LangePirate Return value doesn't count when calculating memory complexity

[@gersimuca]

what does old represent?

[@bhagyshritech2714]

CAN YOU MAKE SOME LIST OF QUESTION WHICH CAN COVER ALL TOPIC OF DSA ALGO for self test

[@odysy5179]

This can actually be done in a single pass using a hashmap as well!

[@talbenjo4841]

how? say you reached a node and its next hasnt been created yet? if you create it on the spot how do you remember to link its previous to it?

[@OdablockShort]

In the second pass, copy just keeps getting overridden each iteration of the while loop since it's not being stored anywhere, so how is this being saved? I'm very confused with the second pass if someone could better explain to me how it works and how it's being stored.

[@amirbayat5713]

how is the list getting created though? cause we are updating the copy each time, without keeping a reference to its head. Help a brother out

[@fernandoluna5458]

Nice solution, but I have a concern about using objects as keys in our hashmap? Is it guaranteed that the hashcode is unique for each object?

[@JayPatel-sl3vz]

yes it is

[@whonayem01]

Thanks!

[@Eda-gm7oy]

I have the final round interview with Microsoft tomorrow, thank you so much for the great videos. If I pass, I will be a lifetime supporter of your channel, promise! :D

[@EverythingTechWithMustafa]

did you get the offer?

[@namanvohra8262]

May you pass!

[@chrischika7026]

did you pass

[@RobinHistoryMystery]

thanks, There is one more solution, Time: O(n), Space: O(1), with a twisted but clever logic

[@abigailiovino72]

could some explain why we need to specify "None : None " ? doesn't this happen automatically when we copy the original in the first loop?

[@khanhchung5207]

because "next" and "random" of a node can be None. This is why he put it there for such cases. My solution in Python just used "get()" to handle these cases. Because "get()" either returns Node or None.

[@CST1992]

This doesn't work with javascript, because it converts objects to [object Object]. I had to add indices to each node (that is, cur) to get it to work.

[@sent4dc]

5:56 what is the 'old' there? where does it come from?

[@kimchhoeu1638]

suppose to be cur

[@MsSkip60]

Would FAANG expect O(1) space solution?

[@eugenevedensky6071]

Absolutely they would, at least G and F would. They would certainly ask a follow up about how you can reduce to O(1) at the very least.

[@chaitanyavarma2097]

fb wants it.

[@pekarna]

Slight speedup: In the 2nd pass, we don't need to iterate over the whole list, but rather just over a "todo list". Which may be empty and save us the whole pass. Runtime: 190 ms, faster than 90.91% of Kotlin online submissions for Copy List with Random Pointer. Memory Usage: 35.8 MB, less than 85.23% of Kotlin online submissions for Copy List with Random Pointer.

[@hhcdghjjgsdrt235]

I submitted the same code. first it was 35 % faster then it was 90 % faster

[@NihongoWakannai]

@@hhcdghjjgsdrt235 yeah, the runtime is completely random when the difference between 90% and 30% is only a few ms. It means literally nothing

[@davidbednar7174]

What's a worse solution?

[@zechenguo9672]

Thanks for the great explanation but I'm confused as to why we can use class objects as dictionary keys? I thought dictionary keys have to be immutable but the Node objects are mutable.

[@pinchonalizo]

What is being used as the dict key is a reference (pointer) to memory, which is not mutable. Python uses references for non-primitive data types

[@Ryukachoo]

it seems like this question has been shoved behind the leetcode paywall? not sure if its just me

[@huansir1922]

very good

[@samzzz6760]

That was written elegantly

[@Socrates225]

Intended is O(1) not O(1) space complexity

[@CST1992]

Man, I cannot BELIEVE it's this easy.

[@sanooosai]

great thank you

[@kaldc4958]

at 6:00 and line 17, we haven't defined old yet?

[@kimchhoeu1638]

suppose to be cur

[@yvanpearson7024]

There's a O(1) space solution, but seems to require modifying the original linked list

[@ap84wrk]

You can still do it with O(1) space and keep the original list. You need to touch it though, but you can just restore 'next' links in the 3rd pass.

[@sahilsharma2867]

I thought dictionary allow only hashable objects to be stored in the key. How could a node be stored? edit: custom objects can be stored as key in dictionary

[@jacktran7044]

One of the issues with this solution is that the class Node doesn't appear to be hashable

[@AmolGautam]

thank you.

[@asder111]

How about just one pass

[@syafzal273]

Can be solved in one pass as follows - class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': cloneDict = collections.defaultdict(lambda: Node(0)) # Edge case/end of list cloneDict[None] = None curr = head while curr: clone = cloneDict[curr] clone.val = curr.val clone.next = cloneDict[curr.next] clone.random = cloneDict[curr.random] curr = curr.next return cloneDict[head]

[@fraserdab]

Dude I think people found new ways to solve and the newer solution is O(1) space

[@ianokay]

This makes no sense for languages which cannot store a complex object as a hashmap key. I'm really not even sure how it's serializing the object to accomplish that

[@eng_bett]

2:58:00

[@monicawang8447]

I have a dumb question..why we can't do "while head:" and "head = head.next" but we can set "curr = head" and loop through curr?

[@sauravpawar5251]

Because head is the original pointer that we will be needing anytime in the future, so it's better not to mess with the original one and if we want to, it's better to use it's copies. In the end, we have used head pointer to return the final value of the function, but if we used head instead of curr, we might lose the pointer pointing at the first node of the linked list...

[@monicawang8447]

@@sauravpawar5251 Got it, Thank you!

[@user-rc2lc2ik6m]

damn good vid

[@nasamind]

Awesome

[@indhumathi5846]

understood

[@garykim313]

Funny, I forgot to update current pointer on second pass as well.

[@bngplays945]

for the entire video I was finding old lol

[@kimchhoeu1638]

suppose to be cur

[@yogendrasinghvimal5043]

This solution here is giving Time Limit Exceeded in Kotlin.

[@yogendrasinghvimal5043]

Here is the Code : fun copyRandomList(node: Node?): Node? { node ?: return node val map = hashMapOf() var trev: Node? = null var temp = node while(temp != null) { map[temp] = Node(temp.`val`) temp = temp?.next } temp = node while (temp != null) { trev = map[temp] trev?.next = map[temp?.next] trev?.random = map[temp?.random] temp = temp?.next } return map[node] }

[@hhcdghjjgsdrt235]

I did it after the hint : We need two passes

[@nicolassilvadossantos9688]

For me makes more simple make this in one loop, follow my example in c# public Node CopyRandomList(Node head) { var copies = new Dictionary(); var dummy = new Node(0); var cur = head; var tail = dummy; Node GetOrCopyNode(Node original) { if (original is null) return null; if (copies.TryGetValue(original, out var copy) is false) { copy = new Node(original.val); copies.Add(original, copy); } return copy; } while (cur is not null) { var copy = GetOrCopyNode(cur); copy.random = GetOrCopyNode(cur.random); tail.next = copy; tail = tail.next; cur = cur.next; } return dummy.next; }

[@ap2s2000]

You can do this in O(1) time without the need of the dictionary ``` class Node: def __init__(self, val=0, next=None, random=None): self.val = val self.next = next self.random = random def copyRandomList(head): if not head: return None # Create copied nodes interleaved with original nodes curr = head while curr: new_node = Node(curr.val, curr.next, None) curr.next = new_node curr = new_node.next # Assign random pointers curr = head while curr: if curr.random: curr.next.random = curr.random.next curr = curr.next.next # Separate the two lists pseudo_head = Node(0) copy_curr, curr = pseudo_head, head while curr: copy_curr.next = curr.next curr.next = curr.next.next copy_curr = copy_curr.next curr = curr.next return pseudo_head.next ```

[@edwardteach2]

U a God

[@tonyiommisg]

This problem is wayyyyy simpler than the description makes it seem. The description of the problem is just obnoxious

[@sreedeepthichigurupati2824]

Java solution: Followed the approach from a different video though with a few differences. kzbin.info/www/bejne/qqC7moSanayZbJY public Node copyRandomList(Node head) { if(head == null) return head; HashMap map = new HashMap(); Node curr = head; map.put(curr, new Node(curr.val)); //create a map with old node, new node. while(curr != null){ Node copy = map.get(curr); // If the curr.random is not in the map, add the original and copy to the map. if(curr.random != null && !map.containsKey(curr.random)) map.put(curr.random, new Node(curr.random.val)); Node randomCopy = map.get(curr.random); copy.random = randomCopy; // If the curr.next is not in the map, add the original and copy to the map. if(curr.next != null && !map.containsKey(curr.next)) map.put(curr.next, new Node(curr.next.val)); Node nextCopy = map.get(curr.next); copy.next = nextCopy; curr = curr.next; } return map.get(head); }

[@iluminatibox9949]

not clear enough

[@tabmax22]

such a gay question

[@NeetCode]

lol

[@Nonsense116]

Totally irrational, but it annoys me how his explanation progressively gets more aggressive. Also explaining the easy part. Like yes, I get copying a node means creating a new node and the next node will also be a new copy. All you needed was a short note about the difference between shallow vs deep copies. Not explaining the next means next and random means random.