Find the Maximum Sum of Node Values - Leetcode 3068 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find the maximum sum of node values so this is a hard problem and 100% I'm going to show you how to solve this problem efficiently but if there's anything you take away from this video hopefully it is how to kind of approach really difficult problems and learn some problem solving skills from it those problem solving skills might not necessarily lead you to the correct solution every single time but still these are useful skills and that's really what I try to so we're given an undirected graph that is specifically a tree so immediately we should be familiar with what a tree is if we're trying to solve this problem if you don't know what a tree is I wouldn't even bother with this problem and I'm not trying to be mean I'm just trying to be honest tree is a connected graph that does not have Cycles in it so no Cycles to worry about the fact that it's connected is really the most important thing and that's going to be very relevant to the rest of this problem because as you may know with a connected graph and specifically this one is undirected there is going to exist a path from any two given nodes in the graph any two given nodes there's going to be a path connecting them so keep that in mind we are also given an integer K so K could be anything this is really the most important parameter because what we are trying to do take this graph for example since it's the simplest one we have a node zero and one now these are like the labels because we're given these nodes in a array so this will be at the zeroth index this will be at the first index but these are not the values of this graph so if you look down here the value of this one is actually going to be two and the value of this one is actually going to be three so I think that's what I'm going to put here the value K in this example is seven the idea in this problem is that we can take any Edge this one is simple there's just a single edge but we can take any Edge and when we pick this Edge what we do is say take this value over here and xor it with seven and at the same time we have to take the other value attached to that edge and exort it with seven as well and the result is going to be the new value for each of these respective nodes and they kind of mention down here in the description that 2 exord with seven is going to be five and three exord with seven is going to be four so these are going to be the new values so then we'd put a five over here and we'd put a four over here ultimately what we're trying to do here is maximize the total sum of all the values of the nodes so right now it looks like we increased them previously the sum was 2 + 3 that's 5 now the sum is 5 + 4 that's nine so we've increased it but this is such a simple example let's go again let's see if we can notice anything let's try to make it even bigger now I'm going to take five and now I'm going to exort it down here cuz we have some empty space I'm going to exort five with that same number K they don't really tell us in this problem we can't do that same operation on an edge multiple times so screw it that's what I'm going to do 5 xord with seven and four exord with seven the result of this one is going to be two and the result of this one funny enough is going to be three does that look familiar to you it does to me it looks like we just got the original values back again um is that a coincidence because when I'm looking at a problem like this one the first thing I'm trying to do isn't actually solve the problem because this is a hard problem I wouldn't be able to solve it in a few minutes I don't immediately read this and automatically know how to solve it I start to look for Clues and one of the clues I was looking for is this operation that we're doing here is the xor operation right they tell us what that operation is like well they don't tell us what it is but we know what it is but basically it's not like some random operation that we're doing what I'm getting at is this operation is not a black box we can possibly get some clues about how to solve this problem or optimize this problem by thinking about what this operation is actually doing take a look at this let's look at this when you have two exord with 7 in binary two looks like this uh 0 1 0 seven in binary is this this is one this is two and this is four so if you add those up then you get seven so if we exor this we're looking for the spots that that there's only a single one so we put a one over here there's a double one over here so we put zero there's a single one over here so we put one in other words when you look at the original number either what's going to happen a zero could possibly turn into a one if that happens like from the original number a zero turns into a one like uh down here that must mean that there was a one over here and then on the next time if we take this same exact number number and try to exort it with the result of this then we're going to turn that one back into a zero cuz now we have double ones over here if you have a one and you turn it into a zero then the next time you exort it with the same number it's going to be turned into a zero and of course we could look at the case where you have double zeros and double ones that's kind of what we're doing here actually but ultimately the biggest thing to notice about the xor operation is if you have some integer n and then you exor it with a given integer K and then you exort it with that given integer K again the result is always going to be n this is a key observation if there ever existed a key observation in any problem but even this is not enough let me tell you one more hint and I bet you'll be able to solve the problem without even watching the rest of this video remember what I mentioned earlier that any two nodes are connected well let's take a look at this example and really drive that point home we only have two edges here so it's a little bit more complicated than this example but still it's pretty simple suppose I take this Edge and I do that exor operation okay so we end up xoring this one a single time we end up xoring this one and then suppose I choose this Edge so we end up xoring this one twice and then exing this one Once In other words we exor this one twice so we don't actually change it we only end up changing these two now suppose to make it even more interesting I introduce a new node over here and now I say I'm going to exort this one twice because I choose this Edge and then I exort this and I also exort this in other words we don't exort this one at all so let me just redraw this this would be the result this one gets exord and this one gets exord and then these two in the middle actually stay the same and if there was like some path here we could continue doing that so what we're noticing here is very very important we already know that if we choose the exort operation we have to pick an edge therefore we have to exort two nodes but those two nodes actually don't need to be adjacent it's true that we can't just pick one node and exort it that's 100% true we can't just pick one we have to to exort two nodes at a time but those two nodes don't have to be connected by an edge they can actually be anywhere in the graph any two nodes at a time that's what I'm saying that this problem the way it was worded was actually wrong we have discovered a simpler version of the exact same problem we've rewarded the problem we changed it now we're allowed to pick any two nodes in the graph and xor them at a time given this information can you now solve this problem in a relatively efficient way well I'm going to show you exactly how to so what we're realizing is that for any given node we really have two choices either we leave it the same or we exort that node but also keep in mind that if we exort any given node we must exort at least another node any other node in the graph this is like our choice right we either exort two nodes or we don't do anything of course for any any given node it only has two possible values the original value or the exord value so it's not like there are an infinite possibility of values that any node could be so this is kind of simplifying the problem given this I think there actually are multiple ways to solve this problem I'm going to show you the one that I was able to come up with by myself I think it's a relatively simple one um maybe there's a more simple one you can feel free to talk about that in the comments I guess if you found a better one remember that ultimately we are trying to maximize the total sum of values so we'd only want to do an xor operation if we increase the total sum of values so what we should do is first of all just look at the Delta which values are going to end up being increased by the xor operation and which ones are going to be decreased let's go through every single value and figure out the Delta after xoring it and to make this interesting let's look at the biggest example actually it looks like all the values in that are the exact same so that's not going to be too interesting let's uh focus on this one so I'm just going to add like the actual value of every single one of these next to it so I think this one is a one this one is a two and this one is a one based on this down here and K is equal to three in binary this is one in binary this is two in binary this is three if we were to X or one with three so we' take these two and exord them it would look like we'd get two as a result so I'm going to put the exord version second so this is going to be a two and so obviously this one would end up being the same and two exord with three down here is just going to be one So that obviously makes sense cuz two is going to be turned back into one so we'd expect a two to be turned into a one okay so just to draw it a little bit bigger this was our original array of nums now now we create another array that I'm going to call Delta and that is for each of these was this one increased or decreased when we exort it well it turned into a two which you can see like over there so obviously the Delta was A+ one two turned into a 1 so the Delta was a negative 1 and then this turned into a two so the Delta was a plus one okay now this is what we care about like this is our original sum so let's just say that so far the total happens to be four originally can we increase that total at all well we can pick this + one Delta we can pick this plus one Delta and then add two to the total well imagine for a second that this input array was actually all ones three ones and then this was also like a plus one over here would we be able to pick all three plus ones you tell me based on what I told you earlier would we be able to pick all three of these no there's a reason for that try to think about it this is an odd number remember we can only pick two at a time so in the context of this problem when I say I'm picking both of these this one and this one I'm saying that I'm choosing this path I'm picking this node to exor and I'm picking this node to exor and I'm choosing this path and obviously if this graph was a little bit different like if this part was like the one and this one was like the two I know this is really messy I'm sorry about that but basically what I'm saying is then we would have chosen this node to exor and this node to exor therefore we would be choosing this path over here that kind of looks like an A or whatever like this notice that these two nodes are not adjacent to each other but they are connected by a path therefore this one does not get exor that's what I'm saying okay now knowing all of that if you believe me how do we solve this problem programmatically we can't just look at the Delta array and just pick them well this is the part where we get really really greedy and we take the Delta array and we sort it in descending order because we want to pick the biggest guys and we want to put all the big values at the beginning so that's what we're going to do we're going to take Delta array we're going to sort it it's going to look like this 1 one and negative 1 we're going to go two at a time like we're going to look at two adjacent values each time we're going to look at both of them we're going to add both of them up and we're going to say is the sum of these two positive is it greater than zero if it is go ahead and add it to the total and keep going now look at the next two values well this time there aren't two values left right so this is the part where we say okay we can't do anything like there just aren't enough values to look at so even if this one was a plus one we wouldn't be able to add all three of them now to make it I guess a tiny bit more interesting let's go ahead and actually add a negative one over here I guess in the context of this problem that would pretty much mean creating a node over here that has a value of two so this is the value and then it turns into a one after we exor it so we do have two values left this time but should we add them to the total probably not cuz why why would we They Don't Really contribute anything they actually make our total even smaller so we don't include these we do include these we get a total of 2 + 4 that's going to be six it looks to me that is the correct result of this problem so this is the explanation of the problem the overall time complexity is going to basically be bottlenecked by the Sorting that is going to be n log in but I do think there actually are other solutions to this problem that actually are just Big O of n but I feel like this is such a hard problem that I want this video to appeal to a wide variety of people that I think showing you this slightly more simple and slightly less efficient solution is actually fine cuz this one does pass as well I would hope that in a real interview this would most likely be enough I really really believe that even at Google this would more than be enough also I want to say that this is harder than the average problem you will see at a company like Google 100% And if someone does ask you this question they will almost certainly give you some hints just like I did in the video also of course we do use extra space so space complexity is going to be big oent let's code it up so I guess before I actually clear this I might as well show you like this is how I was able to like approach this problem again like this is a very difficult one don't feel bad if you weren't able to solve it by yourself this was like my main thought process it may or may not help you but let's actually get into the solution now we know that the main way to solve this problem is going to rely on this Delta array in Python it's pretty easy to actually get it we're going to use something called list comprehension so for every number in in the input we want to map it to this we want to take n and exort it with K of course but that's not the Delta right that's just the new version of that number to get the Delta we take the new version and subtract the old version so either it increased or it decreased maybe it stayed the same but overall we care about the Delta and remember we want to sort this as well we're going to sort it in descending order you could I guess sort it in ascending order if you wanted to and then just iterate over in reverse order but why would we do that and we want to obviously compute the result which is going to be the maximum sum of all the values and then return that and initially we actually don't need to set it to zero we actually can set it equal to the sum of the input and then now we can try to maximize it so remember we're going to look at values two at a time in the Delta array so I'm going to say for I in range in Python you kind of have to do it like this so from zero all the way to the last index I guess length of nums this will pretty much be the last index though since this is non-inclusive in Python and also we want to increment our ey pointer by two every single time so that's what this is saying now what I'm trying to do here I guess is take the value at index I in Delta and take the value at index I + 1 in Delta now immediately you can see we might not have an i + one what if we were given an odd number of values we're not going to have an i+1 at some point so before we even do that computation we don't want an index out of bounds let's just say if I is the last Index right now then we don't have a plus one and at that point we should just break out of this Loop okay so if that's not the case then we compute this sum we call it our path Delta or you could say the total Delta it doesn't really matter at this point this isn't really a graph problem at all so we don't really need to call it the path but oh well of course we want to take this path Del and add it to the result but we only want to do that if it's positive in other words if at any point we get a path Delta that is less than or equal to zero at that point we're never going to increase our result anyway remember this array is sorted if these two aren't greater than zero then there's not going to be any values greater than zero in the rest of the array so at that point we might as well just break out of it this is the entire code it doesn't look too difficult does it but remember this first line over here is the hard part it relies on quite a bit of intuition to come up with so I'm going to go ahead and run it as you can see on the left it works and it is shockingly efficient even though there are linear time solutions for this problem that just kind of goes to show you that leak code is pretty random if you found this helpful check out N.O for a lot more thanks for watching and I'll see you soon