Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum fuel cost to report to the capital this problem is really tricky but I'll break down my thought process and then you'll kind of realize that it's not magic there are logical steps that you can follow to solve these types of problems so we are given a tree now it looks like a regular graph but it will have the properties of a tree in that it will be a connected undirected graph without any Cycles that's going to be really really important this graph doesn't have cycles and we want to calculate the minimum fuel cost now the way we calculate the cost is that this is our Target position node 0 and then every other node will basically need a path to connect it to node zero we know that's going to exist that path will exist this is a connected graph and there's not going to be any Cycles in any of these paths but it's not as easy as calculating just like the entire Edge length that would be really easy we would just say the total is three but we also have another restriction which is the number of seats I'm not going into the context of this problem because I don't think it really matters too much but we need a path from every node to a node 0 which I guess I'll call the root and I think this problem makes a lot more sense when you actually draw the graph as a tree because now we can make things even more complicated but it's not super complicated as I'm going to show you in just a second so this is sort of our root node and what we want is a path from every node to the root node now to actually calculate the minimum fuel I said we have another restriction which is we have the number of seats so for example if we start at this node four this node has a car that will drive it to the root node every node has a car that will do that for them and then to calculate the fuel for every car for every node we will just have to get the path length so for this one the path length is one for this one the path length is one for this the path length is one and for these two guys on the bottom the path length will be two but like I said we have something called number of seats if every car just has a single seat then yes we'll have to do it the way we just described but what if every car actually has two seats well for this node it doesn't matter the path that takes it to the root is length one and this guy's not going to be visiting anybody else along the way same for both of these what about these two nodes when four is driving to the root node why doesn't it just pick up this guy as well then we can just take one car that will drive both of them to the root it's basically carpooling now if this guy then all also wants to drive to the root he kind of has to go by himself because this person will already have been picked up so then how should we actually compute the minimum fuel well there's many approaches you might first think of which could be depth first search from every single node maybe from every single leaf node like from here we actually create those paths and then calculate the fuel but it's actually even easier than that and the easiest way to recognize it is by in my opinion drawing it out like this because there's never going to be any Cycles so for us to know the amount of fuel it takes for this guy to get to the root we could also ask ourselves how much fuel does it take for the route to get to this guy and when you start looking at it like this then the sub problems become clear as well because recursively we don't want to have to keep track of every individual node and then calculating the total fuel is going to get complicated that way why don't we ask ourselves in terms of sub problems how many people are going to be at this node that are going to travel from that node back to the root it will never overlap with any of the other sub trees because remember this is an acyclical graph so however many people end up here in this case it's just one and let's say our seat capacity is equal to two there's one person here and they need to travel a distance of one how much fuel is that going to take them well we don't measure fuel based on people we measure it based on cars so what we'll do to get the number of cars that we need to get this person we would just say one divided by the total number of seats which is two but that's going to round down and give us zero so we actually want the math ceiling of this value which is going to give us one we're going to round up because we want to know how many cars is it going to take to take this many people one person now if we wanted to take two people with a capacity of 2 then we do 2 divided by 2 and then take the ceiling of that which is just going to be one what if we needed three people then we'd say three divided by two take the ceiling of that we'd say we need two cars to take three people that makes sense so in this case we need one car to take this person to the root how much fuel does that take well we take cars and in this case we're traveling a distance of one so we take the cars and multiply that by one which is just going to be the number of cars and we only had a single car for this guy so it takes one fuel to bring this node up to the root now recursively before we even do that we would go to this node and say well how long is it going to take or how much fuel is it going to take to bring all of its children up to it now of course this guy doesn't have any children so we didn't do that but the easiest way to do this recursively is to do just like I'm saying by returning the total number of passengers up to the parent node but we should also keep track of some some Global result variable or maybe some Global fuel variable a better name for it and then we can update this within our recursive function but finishing up the rest of this walkthrough for two we want to know how many passengers is it going to have that are going to need to go up to the root well let's go to its children we go down to four how many passengers does four have it doesn't have any children so we're just going to return one up to the parent and then same thing from five we're going to return five up to the parent so there's going to be two passengers that this is going to return to its parent but before we even do that how much fuel would it take to bring these guys up to this well for each of them we would do the same computation we did with this guy which is we'd get one car for one person here one car for one person here for each of them to go up it's going to take one fuel so we'll have two total fuel that it took to bring them here so we had two people here that we got from the children but let's not forget about this guy so we actually have three people here which we are gonna then return up to our parent and then the parent is gonna see three people three divided by our capacity which is two that means it takes two cars to bring them and to go a distance of one with two cars it's gonna take two fuel to get there now we haven't really been keeping track but I think we're at about five total fuel by now and then lastly we'll have this guy which is going to take one fuel to bring him to the root so in total we'll have six fuel for this problem the minimum amount of fuel it would take in this case that's pretty much the problem as you can see we're mainly just doing a depth first search starting from the root so the overall time complexity is going to be Big O of n we're not using any extra memory but in the worst case we will have the call stack which will be the height of the tree which in the worst case will be log n if it's a balance tree or just o of n if it's an unbalanced tree so now let's code it up so the first thing I'm going to do is build an adjacency list and I'm going to use a hash map called a default dictionary in Python where the default value is a list so we're going to go through every Edge in our roads I guess that's what they're calling it here in roads and for every Source node I guess calling them source and destination doesn't make sense in this problem because they are undirected but we're gonna do the same thing for every source and every destination just appending its neighbor to the adjacency list then I'm going to have a result variable which I'm going to initially set to zero and that's the variable we're going to be returning and we're going to be running a depth first search before we return the result within our depth first search we're going to start at some node we are going to use a second parameter which is going to be the previous node and you'll see why in just a second but that's that's the only other parameter that we're going to need and inside this DFS we're going to declare our result variable as non-local because then when we actually update it within the DFS we will be updating the value outside of here otherwise we're going to get an error but we will still have access to the adjacency list and everything else from out here within this function but for the DFS what we want to do just as I mentioned is total up the number of passengers so initially I'm going to set that to zero and what this DFS is going to do is return the number of passengers it's not going to return the result we're going to be updating the result within here but I think it's cleaner to write it this way with having like a global or non-local variable like this now for the node finally we're going to go through all of its children so for child in the adjacency list of this node now the one thing we don't want is to get caught in a cycle now since we don't have have a connected graph we're not going to have real Cycles here but from a child we should never be able to go back up to the parent so maybe instead of calling this previous I should call it parent and if a child is equal to the parent then we want to skip or rather if this is not equal to the parent then we want to actually execute our code here which would be to run DFS on that child and we're going to pass in its parent which is the current node that we are at so we're going to run DFS on here it's going to return the number of passengers from that child node let's assign that to P because we're going to need it twice one obviously we want to take our current number of passengers and increment this by P but also we want to be able to update our result so how are we going to update the result well first of all we're going to get the number of passengers divided by the number of seats and we want to take the ceiling of this because this is going to tell us the number of cars that we're going to need and I think in Python you also need to declare this an integer or cast this into an integer because even though this value should evaluate to an integer it might be declared like as a decimal like 4.0 or something like that at least in Python so this value though which is an integer and it's the number of cars that we have which is also equal to the number of fuel it would take this many cars to go one Edge which is why we can just take this and add it to our result and that is more or less the entire code now there's a couple things I want to fix when we're returning the total number of passengers we're getting the passengers from all of our children but we also have to consider the original node itself and the reason I'm going to be adding that down here is because we don't want that to factor into our result calculation because we're calculating how much fuel it would take for these passenger managers to reach this node it's not going to take any fuel for this node to reach itself so that's why we're adding this at the end now lastly let's actually call our DFS it's pretty easy to forget to do that so calling our DFS starting at the root node which is zero and it's parent I guess we can just give a value like negative one because none of the nodes are going to have a value of negative one so this is 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 neatcode.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon