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!

[@bernardpark3196]

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

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

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

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

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

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

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

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

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

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

[@htoomyatnaing5775]

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

[@kushagrabansal2107]

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

[@alexshay7969]

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

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

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

[@GoziePO]

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

[@rockywu5502]

So simple and elegant, just wow.

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

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

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

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

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

[@KarthickSubramanian-k8t]

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

[@lovuitchen9332]

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

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

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

[@wlcheng]

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

[@tien-yuhsin2095]

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

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

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

[@symbol767]

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

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

[@RobinHistoryMystery]

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

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

[@木漏れ日-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})

[@bereketyisehak5584]

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

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

[@ManojBaruahadams]

Nice explanation with pass1 and pass2.

[@chenhaibin2010]

that is the youtuber worth its name. Thank you

[@mohamedantar1249]

Best explanation ever❤

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

[@vandananayak9426]

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

[@ehsank7046]

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

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

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

[@aishwaryaranghar3385]

Thank You sir! Your explanations are the best!

[@fraserdab]

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

[@NeilSharma-u5n]

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

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

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

[@kowshiksai]

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

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

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

[@gersimuca]

what does old represent?

[@jacktran01]

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

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

[@ssuriset]

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

[@akhma102]

Thank you, Neet!

[@sachinkolachana6384]

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

[@MP-ny3ep]

Superb Explanation !

[@priyavardhanpatel6155]

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

[@namanvohra8262]

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

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

[@Socrates225]

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

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

[@aliciasuper7014]

Amazing explanation

[@NeetCode]

Happy it was helpful 🙂

[@rohanpaul2504]

This is genious of a solution !!

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

[@zhe7518]

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

[@davidbednar7174]

What's a worse solution?

[@kratiyadav378]

I have done it in one-pass iterative createCopy(node, map) -> returns the cloned node if present, else create copy of the node, store it in the map and then return the cloned node. First we get the cloned node of the original node using createCopy() function then we assign the next node of the cloned node -> get/create copy of original next code using createCopy()function then we assign the random node of the cloned node -> get/create copy of original random code using createCopy()function """ # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """ # USING ITERATIVE # TC: O(N) SC:O(N) class Solution: def createCopy(self, node, clone_map): if node in clone_map: return clone_map[node] elif node: clone_map[node] = Node(node.val, None, None) return clone_map[node] return None def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if head == None: return head # map original node to new node clone_map = {} node = head while node: copy_node = self.createCopy(node, clone_map) copy_node.next = self.createCopy(node.next, clone_map) copy_node.random = self.createCopy(node.random, clone_map) node = node.next return clone_map[head]

[@monarahmanimehr8365]

great explanation!!!

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

[@bhagyshritech2714]

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

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

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

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

[@leul1407]

Thanks very helpful as always.

[@quirkyquester]

this is a fire video brother!

[@yanxu9167]

very helpful, very clear! Thank you for sharing.

[@Ryukachoo]

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

[@CST1992]

Man, I cannot BELIEVE it's this easy.

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

[@Prohduct]

great explanation

[@samzzz6760]

That was written elegantly

[@santiagolimas2014]

Thank you!

[@tonyiommisg]

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

[@Wanderor1]

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

[@an4220]

just mind blowing!!

[@anyalauria1364]

brilliant as usual

[@asder111]

How about just one 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; }

[@kaldc4958]

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

[@kimchhoeu1638]

suppose to be cur

[@kavinarasu8197]

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

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

[@sent4dc]

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

[@kimchhoeu1638]

suppose to be cur

[@eng_bett]

2:58:00