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!
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.
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
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!
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?
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)
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
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!
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.
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
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.
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.
@@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.
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
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!)
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 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.
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)
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
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!
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.
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.
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.
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?
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.
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.
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
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)
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
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...
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 ```
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!
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.
My bad again, just realized that I wasn't updating the dictionary correctly, so I can confirm that it works.
NeetCode gives the best Leetcode explanations on TH-cam, imo
You were right, it's much easier to understand the solution by looking at the code than to explain it. Well done!
Just wanted to say you are awesome, and thank you for your time and effort that you put into your videos! Much appreciated 🙏
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
in c++ to use unordered map you'll need to create own hash function for non standard objects)))
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!
Yes, I did it in one pass too as you described.
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?
I came up with very complicated solution and was amazed to see ur simple solution.Thanks a lot for your time and efforts
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)
genius
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
There is not a single Neetcode video that doesn't help me understand a problem. Much love and appreciation!
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!
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.
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
thanks man
yup never figuring this out on my own lol
I just thought about exactly the same approach :D
Clean, concise and good, as always! Thank you!
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.
That's a good idea!
You could also use Map in JS. It supports objects as key.
@@AdemsPerspective nice suggestion, I’ve found it performs better than hash map, too.
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.
@@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.
Please do more problems. I really love to watch your explanations after I give the problem a try.
My mind just got blown. How was I not able to think of using a hashmap at all?
Same
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😂😂
So simple and elegant, just wow.
Who would have thought this approach in thier first try? Not me..
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
Thank you Fords!! I'm not well versed in Python, but when I looked at your Java code it's very clear.
I really like this problem! Thanks for making these videos to help us all see the algorithms and thought process clearly!
Wow this is such a simple and amazing explanation, thank you, liked!
that is the youtuber worth its name. Thank you
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!)
Thanks, and I'll definitely continue!
The interweaving approach can also be considered the better solution due to its O(1) space complexity while maintaining O(N) time complexity.
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.
By creating the deep copy you will automatically have O(n) space, otherwise it would not be a copy
damn you're right XD@@glennquagmire9572
@@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.
@@ap84wrkWhat do you want tell me with that? If you have to create a copy you can never achieve constant space.
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)
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
did you get the offer?
May you pass!
did you pass
Best explanation ever❤
so when copying old nodes to copy, did you copy the references to next and random?
There is also one optimal solution to this which avoids the extra O(n) space of the hashmap.
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!
actually someone pointed out that by creating a deep copy you're already at O(n) space... so rip XD
@@LangePirate Return value doesn't count when calculating memory complexity
This can actually be done in a single pass using a hashmap as well!
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?
I come up with the same idea but your code is much more concise. Great content!
Would FAANG expect O(1) space solution?
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.
fb wants it.
Thank you, Neet!
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.
Just ran to this question on leetcode today. Thanks for the video!
Thank You sir! Your explanations are the best!
great explanation!!!
Nice explanation with pass1 and pass2.
I just thanked god when I found yoursolution for this problem.
i figured you would go over the interweaving node solution but oh well.
damn bro you just killed it man..... really love your solutions. Thank you so much.
what does old represent?
In the first pass what if 2 nodes have the same values, hash map will overwrite the first one right
Amazing explanation
Happy it was helpful 🙂
could some explain why we need to specify "None : None " ? doesn't this happen automatically when we copy the original in the first loop?
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.
thanks,
There is one more solution, Time: O(n), Space: O(1), with a twisted but clever logic
Superb Explanation !
Thanks. Would google expect a constant memory solution for an L5/L6 SDE role?
We can also do it in one pass by creating the copy of the random node as we go.
Thank you!
this is a fire video brother!
This is genious of a solution !!
So, the bruteforce is the optimal? I had the same thought... hashmap. That's cool though.
What's a worse solution?
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.
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.
Thanks very helpful as always.
Man, I cannot BELIEVE it's this easy.
Is it possible to do it in one pass using a hashmap?
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?
Yeah right, this is why in the video he added the pair None:None in the hashMap.
very helpful, very clear! Thank you for sharing.
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?
yes it is
Hey man! This was really helpful. Thank you so much!
CAN YOU MAKE SOME LIST OF QUESTION WHICH CAN COVER ALL TOPIC OF DSA ALGO for self test
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.
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
One of the issues with this solution is that the class Node doesn't appear to be hashable
That was written elegantly
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
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.
I submitted the same code. first it was 35 % faster then it was 90 % faster
@@hhcdghjjgsdrt235 yeah, the runtime is completely random when the difference between 90% and 30% is only a few ms. It means literally nothing
great explanation
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
it seems like this question has been shoved behind the leetcode paywall? not sure if its just me
Thanks! Was able to come up with the recursive approach pretty quickly after learning from your clone graph video!
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)
brilliant as usual
at 6:00 and line 17, we haven't defined old yet?
suppose to be cur
Intended is O(1) not O(1) space complexity
very good
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]
thank you.
There's a O(1) space solution, but seems to require modifying the original linked list
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.
How about just one pass
great thank you
5:56 what is the 'old' there? where does it come from?
suppose to be cur
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
Dude I think people found new ways to solve and the newer solution is O(1) space
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?
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...
@@sauravpawar5251 Got it, Thank you!
2:58:00
for the entire video I was finding old lol
suppose to be cur
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
```
i hate this problem because brain hurty but i love this solution because its smart
An east medium for once!
understood
Funny, I forgot to update current pointer on second pass as well.
This solution here is giving Time Limit Exceeded in Kotlin.
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]
}
damn good vid