Maximum Twin Sum of a Linked List - Leetcode 2130 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum twin sum of a linked list we're given a linked list of even length that's going to be really important here and that's because every single node in our linked list is going to have a corresponding node on the other side of the linked list so the first node is going to be paired with the last node the second node is going to be paired with the second to last node and if we had additional nodes like in the middle they would be paired together with this same pattern now among all of these pairs we want to determine the one that has the maximum sum so not super crazy one possibility would be this pair add those values together we get five plus one that's equal to six that's our maximum so far but let's try every other pair in this case so we only have one other pair four plus two add those together we get six once again so in both cases six is the maximum and that's what we're gonna return but maybe in between we actually have another pair of nodes and those values are like five and seven or something like that then we would take that pair of values see what the sum is it's five plus seven which is twelve that's the new maximum and that's what we would return so among all these pairs we just want to return what the maximum sum is and then return it now what's going to make this challenging is that we have to pair the first value with the last value and then we're basically doing a two pointer technique where we're taking these pointers and then shifting them inwards and the only reason this is challenging is because we have a linked list it's hard to travel in reverse on a linked list if it's not doubly linked one in a way to get around this would be to just dump all of these values into an array then we can use the two pointer technique pretty easily the downside is that we would need another data structure so we would need o of n memory now is it possible to do this without doing that well it's gonna be pretty much impossible to Traverse this in reverse order if the pointers are like this so if we are allowed to modify the linked list then we actually can solve this without additional memory we can do it with constant memory let me show you how we can do that as you might guess basically if we need to reiterate through this from left to right we can do so we can follow these pointers but if we need to iterate through this in reverse order we have to take every pointer and reverse it so we have to do this before we can do our two pointer technique but this isn't going to be super hard we would just keep going going until we got to the middle of the linked list or the second half of the linked list and then Traverse through it and reversing every link and then by the time we got to the end we'd have a reference to this node anyway so then we'd just be able to reiterate through this and iterate through this at the same time now I'm going to actually do a slightly different approach because it's a little bit easier to code up in my opinion and that is I'm going to take the first half of the array and reverse it so what I'm actually going to get is something like this where we take this pointer and point it backwards which in this case is going to point at null and take this pointer and make it point back at the previous node so this is a bit cleaner diagram but now by the time we do this we will we'll do this as we iterate through the linked list so we'll stop once we get to the Midway point and then we'll have a reference to this node and we'll have a reference to this note if we stop at the Midway point and then we'll iterate through these guys in order and we'll go outwards so this will accomplish the same thing it's just that instead of going from out to in we're going from in to out and then we'll be able to get the sum of every single pair and figure out which one is the maximum now the only thing is how do we actually get to the middle of the linked list because we don't have the length of it initially we could compute the length and then find the middle but there's actually a faster or rather a simpler way to do it which is called the two pointer technique which is slow and fast pointer the idea is that if we have two pointers slow and fast if we initialize them to the beginning of the linked list and we increment the slow pointer by one every single time and we increment the fast pointer by two every single time by the time the fast pointer reaches the end of the linked list or it reaches out of bounds of the linked list which would happen in this case so one more iteration we'd move the slope pointer here we'd move the fast pointer twice so move it out here so slow pointer would stop here our fast pointer is out of bounds every time this is going to happen the slow pointer is going to end at the beginning of the second half of the linked list so we can use this to our advantage because that's exactly where we would want to stop anyway and we're also told that the linked list is always going to be of even length so we don't really have to worry about the case where the linked list is of odd length now let's code this up time complexity is Big O of n because yeah we kind of have to iterate through the linked list twice but that's still linear time and we don't need any extra memory so it's constant memory so just as I said we're going to first initialize a couple pointers slow and fast they're both initially going to be at the beginning of the linked list and all we're trying to do so far is just get to the middle of the linked list and reverse the first half of it I'm also going to keep track of a previous pointer that's going to help us actually reverse the nodes so while our fast pointer is non-null and fast dot next is non-null then we want to continue for the fast pointer it's pretty simple we just want to shift it to the right twice we can do that by setting it to fast.next dot next because we guaranteed that the next pointer is going to be no no we don't know about this this might be null then we also want to set the slow pointer equal to slow dot next but we can't quite do this because we'll still need a reference to the slow pointer before we even do this we want the previous to be set to the slow pointer and actually for this node slow we actually want to set slow dot next equal to the previous node so if we do that we'll have overwritten in the values so we actually have to store this in a temporary variable so slow dot next will be stored in temp but after we reverse it we'll set its next pointer to the previous node then update the previous node then we want to set slow to slow.next but not the overwritten value we don't want to set it to previous we want to set it to the actual next node which we saved in temp so I'm going to do just like that then we're going to actually get our results so we'll set it to zero initially but notice how by the time this is completed the fast pointer will either be at the last note or out of bounds since the list is always of even length our fast pointer is always going to be out of bounds but the slow pointer as I showed in the diagram is going to be at the beginning of the right half of the linked list and the previous pointer is just going to be one behind that which in our case is going to be the beginning of the left half of the linked list using that and using the fact that both of of them are of even length we'll just pick the slow Pointer while it's non-null we could have picked the previous one it doesn't really matter both of the linked lists are of even length then we're going to set the result equal to the max of either itself or the current sum which we can get by taking the previous Value Plus the slow value and adding them together this is the left linked list this is the right linked list we're trying to figure out what the max is and we're also going to have to update the pointers accordingly at this point you don't even need to know which one is the left half and which one is the right half because we're just going to shift the pointers the same regardless slow slow dot next and then we will have our maximum and we can go ahead and return it so that's the entire code now let's run it to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neat code.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon