Most Profitable Path in a Tree - Leetcode 2467 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem most profitable path in a tree and as long as the problem description is the solution is going to be even longer It's tricky to come up with I'm not going to lie to come up with the solution to this problem is a little tricky Dicky but it's very interesting it's very useful I think you'll learn a lot from that part of this problem then in terms of coding it up it took me about 40 lines of code to code this up and provided I'm using python a very nice language for these types of problems and from reading the problem to like fully implementing it and passing it on leak Cod it took me like 30 minutes but I think that's a little bit misleading like this problem is very hard I even had a bug when I ran my submission so like this is one of those problems where if you get it in a real coding interview hopefully you're not expected to solve it in like 20 minutes hopefully they give you at least 45 minutes maybe some hints something like that I don't know but let's go ahead and get into it let's mostly focus on this picture over here there's a lot of words going on let's focus on the example so the idea is that we have two people let's call them A and B Alice and Bob Alice is always going to start in this graph at node zero so this graph is an undirected graph but it's also a tree so that specifically means that there is not going to be a cycle in this graph very important to recognize that because I don't think they explicitly mention that so again we're given this Gra graph it's really a tree that's given in the form of a graph we're given like the edges of course we're going to have to probably convert that into something that's easier for us to Traverse I'm going to convert that into an adjacency list so just kind of telling you that up front because that's kind of the easy part of this problem so like I said Alice always starts at node zero the nodes are going to be numbered from0 to nus1 and it's going to be a connected graph that's kind of implied by the fact that it's a tree and Bob is going to be starting at whatever the parameter happens to be we're given a parameter for the starting point of Bob in this case it happens to be at node three so Bob is going to be over here now I'm going to finish reading the rest of this problem I'm going to explain to you the intuition behind the solution then I'm probably going to try to do a bit of a dry run and then I'm going to code up the solution for you and also give you like the Big O run time and all that but one thing I will say is in the past sometimes I tried to explain these problems by really walking you guys through the exact thought process I had when I was coming up with the solution and in the past to be honest I've learned that most people actually aren't looking for that people say they are but I've recorded videos where I kind of went on like some tangents for like a few minutes and then I've gotten comments that people said you spent a bunch of time talking about a bunch of things that did not explain how the solution works and that felt like a distraction to a lot of people so I'm just going to try to do the best that I can it's not always clear what that exactly is you know you can't always make everybody happy but I hope that most people will at least understand what the solution is by the end of this video so in all of this we're kind of given some rules of the game sort of the simulation that we kind of want to run and at the end of that simulation we want to figure out what is the max profit that Alice can have we don't really care about Bob we want to know what's the max profit Alice can have and that's actually a bit more straightforward than you think the rules of this game name are in some sense meant to confuse you let me kind of cut through all the verbosity of this description and tell you what this problem is really saying each of these nodes has of course the label but it has a value here it's in Black so you can't really see it super clearly that's kind of leak code's fault cuz I'm in dark mode but anyways this is a -2 this is a four this is a 24 and a positive six so each of these values represents the total income or I like to call it the a profit that we can get from each node in some cases it's going to be negative in some cases it's going to be positive it doesn't really matter whether it's negative or positive like the solution isn't really going to change based on that and so what we want to do is have Alice Traverse the tree such that she keeps moving down until she reaches a leaf node so in this case she really doesn't have any choices she has to go to node one but then she has a choice she could either go to node two in which case she reaches a leaf node nowhere to go from there and then she will stop she's never going to move back up to a previous node or she could have gone the other way she could have gone this way where Bob happens to have started and then she could have taken this node and then she could have taken this node there weren't really any choices from here she had to go there maybe there could have been a choice there could have been another node over here but in this example there's not it's a pretty simple example so in this case she would will end up here at this Leaf node and so as Alice goes she's going to be collecting the profit of every node that she visits but there's going to be a catch and I'll tell you that in just a bit so that's Alice's perspective now Bob is kind of in the opposite situation we don't really know where he starts he could start at a leaf node he could start somewhere else he's definitely not going to start at node zero that's actually given to us in the constraints so Bob and Alice will not have the same starting point that's pretty good that's convenient for us but Bob in some ways his options are actually limited because his goal is to reach the root node which is where Alice started at node zero so Bob is never going to have any choices because remember we do not have a cycle so here from Bob's perspective there's only one choice he has to move in this direction you could think okay well what if there was another node connected to Bob like over here sure maybe Bob could have moved there but do you see how that's just a leaf node or even even if it wasn't a leaf node eventually it would lead to a leaf node that's not the direction Bob wants to go well now you're probably thinking okay but what if that node was connected to the root somehow well now you see you got a cycle so that's not possible so you got to have a bit of a deep understanding of how trees work if you don't I encourage you to maybe check out some of the resources on NE code. some of the courses might be useful for you but this kind of knowledge is definitely required for solving problems of this difficulty but anyway so now continuing we know that there's only one choice for Bob it's not going to be straightforward for us to figure out what that is like we're here Bob could have 10 different edges coming out of it we don't know which one is going to lead to this node but we know Bob's situation is very simple Bob does not have choices no choices available for Bob he has to go in this path Alice is the one that has choices anyways so Bob's simulation is going to be very simple Bob is here then he's going to take this note and then he's going to take this note and Bob is going to do the same thing he's going to take the profit or income of every single node we don't really need to keep track of how much Bob collects because we're not going to return that we don't really care about that but it's going to be important which nodes Bob visits it's going to be important to know which nodes Bob does collect from because in this problem they say this like let's say I started here and Bob's over here Alice is going to take this profit Bob is going to take this profit and suppose now Alice is here and then Bob is at the same position Bob is here as well well if they land on the Node at the exact same time so let's keep track of the time as we run this simulation so if they land on the same node at the same time they're going to take the profit or even the loss and divide it between the two and we're guaranteed that these are always going to be even numbers so it's going to be easy for us to divide those by two the return value is going to be expected to be an integer regardless now also it's true that if Alice lands on a node suppose Alice was here and Bob they share the profit and then Alice ends up over here she visits a node that Bob's already taken from well then Alice cannot take anything from this node she's going to get a profit of Zero from that node or maybe if there was a loss from that node she's still going to have a loss of Zero from that note Bob already visited it he already took everything Alice has nothing left but then maybe Alice will then visit this node which nobody has visited Bob didn't visit it yet so she can take all of the profit so those I believe are the main ideas from this problem description I'm just going to kind of skim over this just to make sure I didn't miss anything but again what we mainly want to do is return the max possible income Alice could have if she travels to the optimal Leaf note so regardless of any of the paths that Alice takes we want to run the simulation such that she maximizes her profit so I don't know about you guys but as soon as I hear that my brain starts thinking I start thinking crap is this going to be a backtracking problem because it looks like it's going to be a pain in the ass has to code up if it's backtracking to be honest okay maybe not maybe it's going to be a greedy problem if it's a greedy problem we're probably going to need to figure out some tricks maybe make some key observations about this problem or maybe it's dynamic programming which I feel like for this type of problem on a graph that's also going to be a major pain in the ass so when I looked at these three options I thought man I pray to God that it's a greedy solution and then I looked at the constraints of the problem and I saw that n the max value of it could be roughly a 10 to the power of five so that told me it's probably not backtracking and it might be dynamic programming but I'm going to try the greedy solution first because I assume that that one's going to be a bit easier even though it is a bit easier like I said it's still going to be like 40 lines of code in Python so yeah and it it did turn out to be greedy by the way so now let's start to make some observations about this problem believe it or not the most important observations I actually already made for you these are the observations Alice has choices but Bob does not have choices so the fact that Bob does not have choices maybe we can just run the simulation from Bob's perspective we already know somehow we can figure out the exact nodes that Bob is going to visit and after we've determined that and we've computed that can we then run the simulation from Alice's perspective to then try to maximize the amount that she can collect and the answer is yes but the question is how do we do it given the way that we want to like run the simulation and the rules of this game that they've given us well one thing that was kind of interesting to me is even though Alice has choices the traversal from Alice's perspective is actually easier like from here we're just kind of going down and it's pretty easy to figure out how to do that just don't visit like the node that we came from there's not going to be any Cycles or anything like that but Bob's perspective is a bit different even though he doesn't have choices we have no idea which direction to go I mean which direction is going to take us to the route the thing that I realized was maybe the easiest way to figure that out is just to kind of Brute Force this not literally brute force it because we could do a traversal from starting here going in every direction just by visiting every single node a single time and then among all of those paths that we take so starting from here we could possibly take this path we see okay well that was not the root node that did not lead us to the root node okay well we could then go over here take this node and then maybe the next decision we try is to go down here well once again we realize that did not take us to the root node okay well we still have some options from here we could go up and there you go we reached the root node so these are the nodes that we want to say that Bob is going to visit and if you see what I just did on this picture didn't that look like a depth for search yes that's exactly what it is now there are other traversals that you could do the one that just felt the most intuitive to me was a DFS I think that's the easiest way to actually code this up as well but now in terms of marking Bob's nodes visited what do we actually care about like we don't necessarily know that Bob is going to be able to collect the profit from every node that Bob is able to visit in this case Bob visits this and this and this we have no idea when Alice is going to visit these nodes if Alice is going to visit any of these nodes and based on that we don't know how much profit Alice is going to be able to collect for us to determine how much profit she could collect what we should really be doing is tracking the time that Bob visits each of these nodes because then when we run the simulation from Alice's perspective we can also keep track of the time and then as we visit nodes we will be able to determine was Alice at this node first or did Bob visit the node first cuz if Bob visited it then we should not be able to collect the profit or maybe they visit visited the node at the same time in which case we have to divide the profit by two or maybe Alice visited the node first before Bob got there so Alice can take all of the profit and the last case would be maybe Alice is visiting a node that Bob never ended up visiting maybe it would be a this node in which case again Alice just takes all of the profit so I hope that makes sense to you I don't think it's crazy complicated it might not be obvious it's not crazy complicated but yeah implementing all these little things is going to be a pain and by the way the way I'm going to track that is probably by using like a hashmap for every single node for Bob we kind of throw it into a hash map and just Mark the time so let's uh do that let's say for a node three we visit it at Time Zero for node one we visit it at time one and for node zero we visit it at time two you can kind of see that this probably could have been implemented with a BFS as well but I feel like it would have been harder to do that so I just stuck with DFS okay now I'll use a different col for Alice so Alice is starting here at zero and for Alice the difficult thing is that we do have choices so we really have to kind of try every single path to figure out which one would have been the best one I think that's also possible to implement with DFS we could kind of go through every single path figure out which one led to the maximal result but I think it's also possible to do it with BFS that's the one that came more naturally to me but I didn't actually implement the code for the other one maybe the DFS one resulted in a cleaner solution but I thought BFS was fine so BFS will work like this where we will start here and we will make both choices at the same time or maybe we'll have three choices we'll make every choice at the same time so we start here and let me actually Mark the times for Bob so let's say this was zero this was one and this was two for Bob so now I'm here at Time Zero with Alice and I see my time was less than Bob's time so I take all the profit I get that -2 great and then I'm gonna make every choice that I can I only have one choice so I go there and then I reach this node at time one okay it's a positive four looks like Bob reached that node at the same time that I did so I have to divide that profit which is four and then it will be two so I'll add a plus two here to the total profit that I have so far now I make these two choices at the same time I could either be at this node at time to or I could be at this node at time two if I take this node I will get a profit of positive2 if if I take this node I won't get anything because Bob reached that node first so even though I'm drawing the total profit over here what we're actually going to be doing is for each node keeping track of the profit we have so far so here we had like -2 here we got a positive one or positive4 we divided that by two so then we ended up with a total profit of zero when we get to this node we got the positive two so we end up with a total profit of two I'll put the colors in green just to indicate that it's a profit so here positive two and then here what we could have gotten is nothing so we would have had a total profit of zero and then we would have finally for Alice visited this node at time three and looks like nobody visited that node so far it has a profit of six so our profit previously was zero so we can take that six and collect all of it so now at this node we'll have a total profit of six now among all of the leaf nodes there were only two Leaf nodes this one over here and this one over here we breed them at different times this Leaf node was breached at time two this Leaf node was breached at time three this one had a profit of two this one had a profit of six the maximal is of course six so we return the value six on this picture I hope the solution did make at least some sense I encourage you to try to draw it out yourself if it didn't or if you didn't like my choice of DFS or BFS you can try to code it up uh using your algorithms of choice but I'm going to go ahead and code this up now and you can see that we're basically just running a traversal on the graph twice so the total time complexity is going to be Big O of N and that's similarly going to be the space complexity as well if you have any interest in seeing my original thought process when solving this problem this is what it is but just keep in mind I didn't actually write these notes from top to bottom I kind of filled them in randomly that's kind of how my brain works but I will reset this and so the first thing we're going to do is just build the adjacency list from the edges that were given pretty easy to do that I've done it a million times I won't go super in-depth I'm going to use a default dictionary the default value of a list I'm going to go through every Edge unpack the two nodes the edges are going to be directed so I can do this joncy of V1 add a neighbor V2 for it and similarly for v2 add a neighbor of V1 then we're going to do the DFS Bob simulation so I'm going to say uh Bob time is going to be the hashmap or Bob nodes time either way this is what it represents it's a little hash map it's going to map every node that Bob visits to the time that it was visited then I'm going to implement a little DFS to handle that now you might think that we need a visit hash set to make sure that we don't get stuck in a cycle using this TFS but actually recognize that we're given a tree as the input so it's actually even easier to not have a cycle we can do that by having a source node and also keeping track of what the current nodes parent was also let's keep track of the current time that it took us to reach this Source node so the way this DFS is going to be called is like this we're going to say DFS starting from the node that Bob starts at and let's just say its parent is negative one because it doesn't have a parent right now the parent is just used to indicate like the previous node I guess and so maybe a better name for it would be previous we just don't want to get in a cycle where we go from The Source node back to the previous node back to the source node etc etc and we can start at time Z okay so in terms of the base case we know that the main one is when the source is equal to zero that's very good we can return from that and we're going to return true to indicate that this was the path that led us to the root node but before we return let's also Mark the time that it took to reach this node the node is zero or we could also just use source and this was the time it took to reach it now we can do this if the base case did not execute we will go through the neighbors of the current node so neighbor of uh Source the adjacency list and if this neighbor is the previous node we definitely want to skip it so we can just put a continue statement here otherwise we do the recursive case we call DFS on the neighbor and we say okay the previous node was the current Source node and we say okay the time to reach that neighbor is going to be the current time + one and what we want to know is the return value of this function call because if it was true then that means that the current node the current Source node is along the path that it takes for us to reach the root node and so if that's the case we can say okay for the current node as well take it the source node and say okay this was the time for us to reach that node it is along the path to the root so maybe to make that more clear here I can say node on root path and from here as well we want to propagate that return value of true so we can do this return true and outside of that we can return false if this never executes so this part I believe isn't too bad but I mean this on its own is kind of a leak code medium if you ask me or maybe it's close to that at least but anyways let's continue that was the Bob simulation we call DFS so we expect that this is going to be populated after that and now it's time for the more interesting part the Alice simulation which I'm going to do with a BFS so there's many ways to code this up I'm really going to take advantage of the fact that python gives us some things so I'm going to have a Q and it's going to be a double-ended q and so I'm going to initialize it with this it's going to be initialized with a tuple of four different values let me comment what those are it's going to be the node that we're currently at the time it took to reach that node the parent or you could say the previous node so that we don't get stuck in a cycle and the total Prof it along the path to get to that node so we know that the starting point of Alice is always going to be zero so that's pretty easy to fill in the next thing is the time well we're starting at Time Zero the parent of the root node it doesn't really have a parent so we can just say netive -1 and the total profit along the path to get to this node including that node well that's pretty easy and I didn't really talk about this but we're given a parameter called amount it's an array it tells us for every node what's the profit of that that node so we can start here by just saying we have the amount of node zero we know that we're dealing with negative values sometimes so I'm going to actually initialize my result to not be zero but to be float of negative Infinity basically the smallest value you can have in Python and eventually we're going to try to increase this and after that we're going to end up returning it so now this is going to be kind of similar to like a textbook BFS with a small differences so I'm going to say while the Q is non empty I'm going to pop from the queue and I'm going to get four values that's a lot of values to get we're going to get the node we're going to get the time we're going to get the parent and we're going to get the profit and then we're going to do the BFS part we're going to go through all the neighbors of this node so like this and the easy thing is if this neighbor is equal to our parent well then once again we just kind of continue pretty similar to what we did in the DFS over here but otherwise what we're going to say is okay the profit of the neighbor is this at least this is how I like to code it up I try to make it as simple as possible at least for myself I don't know what your opinion is going to be on this code but here I say the neighbor's profit is this we assume that we can collect all of the amount from the current neighbor but we don't know if that's actually true so what we're going to do is have a couple conditions we're going to say if the neighbor is in Bob time I think that's what the hashmap was called Bob times if that's the case well then we need to know does Bob Reach This node first because if he does well then that's going to mean this our current time to reach this node was this so the time to reach the neighbor is going to be time + one but maybe Bob's time was even less than that meaning our time is greater than Bob times of this neighbor node and if that's the case then we have to take that net profit or neighbor profit and set it down to zero because we won't be able to collect any of that Bob reached it first or maybe it's the other case where actually time plus one the time to reach this neighbor maybe I could have put that into a variable uh maybe I should actually to make this more readable let's do that neighbor time is going to be uh time + one so let's do that and then neighbor time over here if that's equal to Bob times of the neighbor well then they have to divide the profit then that means Alice is only going to get half of that so we can set neighbor profit equal to the neighbor profit divided by two okay so this is pretty nice this is a very nice way to deal with figuring out how much profit Alice is actually going to get from the current neighbor node but now how do we update our Q well that's actually not too bad we can do this q. append a big fat tupal and if you forget what values we had that's kind of why I put the comment up there it's going to be the node so the neighbor the time which is neighbor time the parent which is going to be the previous node so that's just going to be the original node and the total profit well the total profit to get to this node was this profit and to that we can add the neighbor profit like this so that's what we append to the queue now there's only one thing left and I like to give you guys a challenge so I'll let you try to figure out what to do or how to do it when do we update our result how do we only update the result for leaf nodes because of course over here I could just say okay set result equal to the max of result as well as the profit of this node but there's no guarantee that this node is a leaf node so how do we do that well what's so special about a leaf node in a tree leaf nodes only have one Edge connecting them to another node so maybe I could put an if statement like this if length of the adjacency list of the current node if the length of it is equal to one it only has one neighbor so surely it's going to be a leaf node right maybe I could do something like this but that's not quite correct either because that would end up including the uh root node which is zero maybe the root node only has one neighbor as well so actually one way to handle this would be to like disclude the root node or what I like to do is actually just take this code and only apply it to the neighbor so I'm just going to put that down here and so then instead of using the node I will use the neighbor and instead of using the profit I'll use the total profit over here so this will ensure that we only apply this condition for leaf node so we only consider the profit of leaf nodes the total profit that is so now you can see my entire code we reached line 44 over here but I did have several comments and a lot of spaces I'm trying to fit this all on the screen at one time I don't know if that's going to be possible anyways here is the Alice BFS portion of the code and up above is the Bob DFS portion of the code of course I had a typo I used Bob nodes instead of Bob times but other than that it seems like our solution was correct it was pretty efficient if you found this helpful definitely check out n cod. for a lot more it supports me a lot thanks for watching and I'll see you soon