Copy List with Random Pointer - Linked List - Leetcode 138

[@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!

[@jeromee-dev]

Haha, that's funny because I tried to do that approach where we create the nodes and add a reference to it in a dictionary in the first pass and then set each node's random property in the second pass. Unfortunately, I got a KeyError exception.

[@jeromee-dev]

My bad again, just realized that I wasn't updating the dictionary correctly, so I can confirm that it works.

[@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!

[@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?

[@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

[@AndreiSokolov-k7j]

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

[@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!

[@leonscander1431]

Yes, I did it in one pass too as you described.

[@htoomyatnaing5775]

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

[@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

[@AyushmanTiwari-u6o]

thanks man

[@tenkara101]

yup never figuring this out on my own lol

[@myhandle370]

I just thought about exactly the same approach :D

[@chrischika7026]

thats not O(1) tho

[@sayanghosh6996]

@@chrischika7026 why?

[@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

[@abhijeetviswa]

Isn't is just a recursive 2 pass solution. The second pass happens in the reverse order of items when the stacks are unwinding. I'd argue this is less efficent because of the additional stack space

[@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

[@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!

[@n-logn]

man i was doing same

[@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.

[@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

[@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.

[@alexshay7969]

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

[@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😂😂

[@lovuitchen9332]

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

[@GoziePO]

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

[@kushagrabansal2107]

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

[@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!

[@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.

[@leafhurricane]

@@glennquagmire9572 Memory used for result is not considered. When someone says the algorithm uses O(1) space, it means auxiliary space is O(1).

[@rockywu5502]

So simple and elegant, just wow.

[@souljarohill8795]

I think showing this with the memory addresses would make it more clear. Basically we made a dictionary where the key is the orignal nodes memory address or in python a pointer to the nodes memory address. The value is the coppied nodes memory address/ a pointer to it.

[@fraserdab]

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

[@symbol767]

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

[@Rajat_Dhasmana]

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

[@Jollez]

I was close, I was going to use a hash set for my created nodes and know to pass over if I already got it. I didn’t get far enough into implementing this to realize that it would’ve cause problems when I had to link those new nodes to further nodes

[@chenhaibin2010]

that is the youtuber worth its name. Thank you

[@phantomhunter7985]

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

[@nachiket9857]

Same

[@chrischika7026]

because yuo are not suppose to know it beforehand, this is the learning stage

[@Hebruwu]

It’s crazy because my first thought is always “hashmap, use a hashmap!” Yet this time I was trying to interlink them in some bizarre way

[@tien-yuhsin2095]

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

[@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

[@mohamedantar1249]

Best explanation ever❤

[@anonymous........]

The interweaving approach can also be considered the better solution due to its O(1) space complexity while maintaining O(N) time complexity.

[@orepajic2625]

A friend of mine got asked to solve this in O(1) space by microsoft, apart from being very difficult to come up with the idea its almost impossible to explain the idea and code it up in 45 minutes (-5 for questions and 10-15 for introduction)

[@pun1sher98]

I solved this using recursive approach of building the list from last to the first node. Anyone else though ofthe same? Btw, this was the first medium problem that I solved on my own! Basically, the hashmap part is the same, but instead of doing 2 passes, build the list from ground up: Maintain a hashmap of which can map old to new nodes, as well as track if the node is already created. From here, try to build the list recursively by creating the 'next' and 'random' nodes of the current node.

[@KarthickSubramanian-k8t]

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

[@ManojBaruahadams]

Nice explanation with pass1 and pass2.

[@aishwaryaranghar3385]

Thank You sir! Your explanations are the best!

[@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

[@RobinHistoryMystery]

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

[@kowshiksai]

In the first pass what if 2 nodes have the same values, hash map will overwrite the first one right

[@wlcheng]

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

[@priyavardhanpatel6155]

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

[@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.

[@vandananayak9426]

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

[@bereketyisehak5584]

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

[@rashikraj7404]

But how is curr hashable here, I was planning to the same but was confused about how to make Node() object hashable here to be used as a key in the dictionary?

[@木漏れ日-v9n]

There's also a way to do this in one-pass using recursion: def _one_pass_recursion(self, head: Optional[Node], orig_to_copy: dict) -> Optional[Node]: if head in orig_to_copy: return orig_to_copy[head] copy = orig_to_copy.setdefault(head, Node(head.val)) copy.next = self._one_pass_recursion(head.next, orig_to_copy) copy.random = self._one_pass_recursion(head.random, orig_to_copy) return copy def copyRandomList(self, head: Optional[Node]) -> Optional[Node]: # return self._two_pass(*args) return self._one_pass_recursion(head, {None: None})

[@kaldc4958]

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

[@kimchhoeu1638]

suppose to be cur

[@MP-ny3ep]

Superb Explanation !

[@akhma102]

Thank you, Neet!

[@tonyiommisg]

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

[@aliciasuper7014]

Amazing explanation

[@NeetCode]

Happy it was helpful 🙂

[@zhe7518]

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

[@gersimuca]

what does old represent?

[@mehmetnadi8930]

I like this solution. but i also like mine :) class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': nodes_to_copy = {} def dfs(node): if not node: return None if node in nodes_to_copy: return nodes_to_copy[node] new = Node(node.val) nodes_to_copy[node] = new new.next = dfs(node.next) new.random = dfs(node.random) return new return dfs(head)

[@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.

[@NeilSharma-u5n]

i figured you would go over the interweaving node solution but oh well.

[@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]

[@kavinarasu8197]

If I drink a shot everytime he says “right” 😂😂😂

[@quirkyquester]

this is a fire video brother!

[@sachinkolachana6384]

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

[@rohanpaul2504]

This is genious of a solution !!

[@ehsank7046]

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

[@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

[@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.

[@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

[@monarahmanimehr8365]

great explanation!!!

[@sent4dc]

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

[@kimchhoeu1638]

suppose to be cur

[@leul1407]

Thanks very helpful as always.

[@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

[@ssuriset]

So, the bruteforce is the optimal? I had the same thought... hashmap. That's cool though.

[@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.

[@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?

[@bhagyshritech2714]

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

[@Prohduct]

great explanation

[@Wanderor1]

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

[@Ryukachoo]

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

[@yanxu9167]

very helpful, very clear! Thank you for sharing.

[@namanvohra8262]

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

[@santiagolimas2014]

Thank you!

[@an4220]

just mind blowing!!

[@anyalauria1364]

brilliant as usual

[@jacktran01]

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

[@davidbednar7174]

What's a worse solution?

[@sj37f8diuta]

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.

[@vedantshinde2277]

Recursive Solution Map map = new HashMap(); public Node copyRandomList(Node head) { if(head == null) return head; if(map.containsKey(head)) return map.get(head); Node newHead = new Node(head.val); map.put(head, newHead); newHead.next = copyRandomList(head.next); newHead.random = copyRandomList(head.random); return newHead; }

[@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!

[@jonaskhanwald566]

Beauty of the code lies in the 2nd pass!

[@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 ```

[@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

[@eng_bett]

2:58:00

[@Socrates225]

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

[@CST1992]

Man, I cannot BELIEVE it's this easy.

[@samzzz6760]

That was written elegantly

[@puneethkashyapapparusu1921]

So..... this solution unfortunately did not work in my meta interview, he asked for a more optimal solution and rejected me. Just a public service announcement.

[@jarynh7800]

were they looking for the o(1) space complex solution?

[@adarshsasidharan254]

@@jarynh7800 probably yes

[@asder111]

How about just one pass

[@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