Evaluate Division - Leetcode 399 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem evaluate Division I don't know if I'm getting Dumber or these Elite code problem descriptions are getting a lot worse well I guess this is one of the early problems but I'm just going to skip straight to the example because it's a lot easier to understand it that way we're given a list of equations where the equations could be given like this and keep in mind that these are strings so A and B are going to be strings and what one of these subarrays represents is a / B so that's what this equation is this equation is similar B / C so every equation is going to be in this form with some numerator and some denominator we're also given a second array of the same size which actually tells us the result of each of these equations so in this case a / B we can see down here it's kind of hard to tell but the value is going to be two so a ID B is going to be 2 B / C is going to be three cool now we are also given a list of queries so that's what green is going to represent and those queries are going to be in similar shape as the equations so it's going to be a sublist in this case one of the queries is going to be a c so what we want is to know the result of a ided c now it's not necessarily going to be true that we'll be able to determine it and if we can't determine it we have to put a NE -1 as the result but if we can determine it then we have to put the value of this equation like what it evaluates to and then we have to build a output array so for each one of these queries we'd have some output value now in this case a / C can we determine it well let's not even think about code for a second let's just try to look at like the math hopefully your algebra skills are good enough to be able to evaluate this a / B is equal to 2 and B / C is equal to 3 well take a look we can kind of multiply these two together and the B over here is going to cancel out the b over here and then we're going to end up with a / C and multiplying two and three together like that's the value of these two equations so 2 * 3 is going to be 6 so we were able to determine it this time I have no idea how we would code that up yet but we were able to get the result of this query which is six and that's what they have in the output as well now a quick Edge case worth mentioning is what if some of these equations are the queries like something like this a / e well we weren't even given an e character in the input so it's definitely not possible to evaluate this so for sure we would put a ne1 in the output and that's what they do for this one it's over here another Edge case and this one I think is kind of dumb I really don't understand this take a look at this over here x x so we don't know what x is that's perfectly fine but x ided x should probably be 1 right unless we have some kind of divide by zero which I believe they mention will never really be the case and we won't have any contradictions so we don't have to worry about that thankfully you would think this would evaluate to positive one but I guess in this case it doesn't over here x / X gets us a negative 1 you can't really see it anymore but it does give you a negative 1 or at least that's the expected result that's kind of stupid in my opinion but okay we just have to account for that the first thing I personally tried was maybe we can just solve for every single variable and then it'll be pretty easy to know the result of every query because they literally are just a divided by you know some other variable that's the form of every single query my math skills are sharp enough to recognize that we actually can't do that in this case we have in this case two equations but we have three variables a b c so we simply do not have enough equations unique equations to be able to determine the value of a and b it's ambiguous and if you don't believe me let me prove it to you let's just say hypothetically the value of a is two then what must be the value of B to get an output of two probably one okay let's say a is 2 B is 1 okay then we get a one over here then what's going to be the value of C probably a fraction in this case 1/3 1 / 1/3 is going to give us three in the output this is one way of solving this equation you can tell this math definitely works out but now let me change it up let me transform a over here to now be a four and transform this to be a two and so that means it's a two over here as well and then that means for this to equal three we have to make this 2/3 this is another way that the equations do work out so what you find is we can't actually determine the value of each variable and clearly this is a very simple example but we could have had a ton more equations and at this point if I gave you this problem in an interview I would definitely expect you to need a hint cuz it's not very intuitive how to solve this problem but actually it turns out we can transform these equations in a graph representation which will allow us to solve this problem notice how when we have a query like a / C we start with whatever we can we start with maybe a / B and at this point we need a way to cancel this B so we would look for all the other spots in our list of equations where B is in the numerator spot because then we can get a fraction in this form something in the denominator who cares it's an X but we can get something in this form where we cancel out like this and we have a / X we don't necessarily know we'll ever be able to figure out what a divided by C is but this is our best bet we have to sort of cancel out the denominator because if we multipli this by something else like If I multiply this by D / e we're not getting any closer to this are we that's a little bit of the intuition and also notice that when we do this B / C we are multiplying the values together so this is a little bit of the intuition of why we want to map every single numerator to all of the possible denominators that it has in any of these list of equations and it could have multiple of course in this case our graph kind of looks like this shape a points to b b points to C now it could have been possible that a you know points to something else like an X in this case though our graph is pretty simple so let's just try to understand this itself can I ask you if we start at a and Traverse the graph and end up getting to B what does that represent doesn't that kind of look similar to this like actually multiplying the equations together this is kind of like a / B this is B / C and what we were doing with these values is trying to multiply them so wouldn't it be kind of good to put the edges as the value of each equation so a / B is equ to 2 B / C is equal to 3 then the way we formulated the problem a path from a to c multiplying all of the edges together must mean that a / C is equal to the multiplication of the edges it's equal to six because of the way that we formulated it I know this is kind of a crazy idea that really isn't common in data structures and algorithms you probably haven't seen it before so it might take you a second to really understand it it but it's pretty simple what's actually going on here now another question you might have is what if we going in reverse order C going to B going to a like that's a perfectly valid query what if they instead ask c ided a well the way I formulated this was a little bit naive now we kind of realize numerators point to denominators sure but shouldn't denominators also point to the numerators as well can't we kind of do this in reverse order can't I also say this equation C / B which is you know the reverse of this reverse of this multiplied by B / a which is the reverse of this isn't that perfectly valid as well that gives us C / a yeah I don't see any reason we can't do that but if we try to multiply the edges going in reverse order we still end up with six so how can it be possible that a / C equals 6 and C / a equals 6 I'm pretty sure that's a contr prediction and it is and that's when you realize when we go in the reverse direction we should take the inverse of these values cuz that's exactly what these are these are the inverses of each other if you don't remember what an inverse is it's basically 1 divided by this number so what we essentially learned here is that our graph is going to be directed The Edge going in this direction is not going to have the same weight as the edge going in the other direction this one will have a weight of 1/ 3 and this one will have a weight weight of 1 / 2 so this is basically how you need to formulate the problem in order to solve it is it intuitive not for me but I hope it's starting to make sense for you and I'm a big math fan so I thought this was one of my favorite problems I ever solved okay so knowing all of that how are we actually going to solve the problem well first we're of course going to have to build this graph essentially just building an adjacency list using these as our edges and we are given the values as well those are going to be the weights of each Edge and we're going to build like the reverse Edge as well and then for every single query we are kind of going to do it a Brute Force approach which thankfully is good enough for this problem cuz it is a medium so I think that should be perfectly fine and by Brute Force I mean on the graph for every single query we're either going to run a depth first search or a breath first search so potentially traversing the entire graph I believe the time complexity is going to be n for the number of queries multiplied by the size of the graph which I believe is e+ V where Edge plus vertices to simplify this I think just having e for like the length of the equations is probably sufficient n * e where this is the number of queries space complexity should just be the size of the graph which is going to be V plus e so now let's go ahead and code this up like I said first step is going to be building the graph in Python what I'm going to do is create a hashmap collections. default dict where the default value is going to be a list because what we know is we're going to map every numerator or just every number a such that it's mapped to a list of pairs where each pair is going to be B where B is just a variable and the second value is going to be the evaluation of a divided B if this doesn't make sense don't worry it'll probably make sense as I actually build this so what we're going to do is iterate through every equation but in Python we can do it like this for I equation in enumerate the list of equations reason I'm using a numerate is we not only get the value from equations which is here but we also get the index as well which just saves us a little bit of boiler plate and then we can unpack the variables from the equation cuz we do know it's a pair of variables we know we want to build directed edges so from a we're going to append the neighbor B and what is the evaluation of a divided B well thankfully that's going to be stored in values at index I you can see why we needed the index I now and we also know we want to do the same thing going in the opposite direction so we might just say B / a but there's a bug remember it's not going to have the exact same weight so we want to take the inverse of this so we say one divided by that in Python one slash means decimal division which is exactly what we want in this case if you're using like Java I think that'll be energer division so you want to keep that in mind but next we just want to run every query and get the result of it we can do that with a DFS or a BFS I'm going to do BFS the main reason is it's easier to handle cycle detect protection and it's possible that our graph could have a cycle so BFS just makes it a little bit easier for us what I'm going to be passing into our BFS is going to be the source and the Target and what that's going to be in this case is if we were given a query like a / B then the source is a and we want to find a path starting from a getting to B and once we get to B we just want to multiply the weight of all those edges and return that so that's what this is going to be doing so before I even implement it I like to show you how I'm actually going to be using this so for every query in our list of queries we want to call BFS passing in Q at index0 as the source and Q at index one as the Target and we can use this to build an array but in Python we have a nicer syntax called list comprehension so we can build a list just like this by putting a for Loop inside of it so for every query this is the value that we want to add to the list and it will execute in order as well so this is the result that we're going to end up returning and now all we have to do is actually implement the BFS and before I forget I want to say that remember if any of the source or the destination is not in our list of equations which means it's not in the adjacency list then we want to return -1 immediately even if we're given something where the source and the target are equal like I said I think that's kind of weird x / X should always be one but in this case they want it to be negative one I guess so if source is not in the adjacency list or Target is not in the adjacency list we return ne-1 now we have our pretty cookie cutter bread for search where we're going to need a q and a hash set and I'm going to use a deck and a hash set like this we initialize our Q just starting at the source but I'm actually going to also add a second value because remember we do want to keep track of the multiplication of all the edges but since we're not doing this in like a depth first search way where we might go to A to B to C Etc we're doing it layer by layer we could start at a and then the next layer could be something like a and d and then the next layer could be something like c and e so we want to simultaneously keep track of the multiplication of these edges and these edges so instead of having a bunch of variables to do that we can just use the Q itself every time we add a value from our graph to the Q we're not just going to add the value we're going to add the total multiplication of the edges so far what do you think would be a good starting value for our source node to have for the like multiplication probably just one cuz it's a neutral value any value multiplied by one will end up being that value and I also like to immediately add to the hashset The Source node and then we want to do a BFS so while the que is not empty we want to pop from the que we're going to append to the right so we want to pop from the left and when we pop we end up getting the node and the weight I'm going to store that in N for node W for the weight and you might think let's immediately just start going through the Neighbors in the adjacency list of the node n but remember before we do that we're looking for the Target if we find the target there's no point in continuing we're not doing this for fun we're looking for the Target so if we get to a point where n is equal to the Target then we can go ahead and return what should we return weren't we trying to multiply all of the weights well yeah but remember when we append to the que we're going to be appending the multiplication up until this node so w is already the value we want to return so just go ahead and return it here okay we have that handled and we know actually this might not always execute so to be safe let's put A1 over here it's possible that both the nodes exist in the graph but there just happens to not be a path connecting them in that case we would return ne1 but now as we go through every neighbor of this node we remember that we're not just going through the neighbor we're going through the pair which is the neighbor and the weight so the second parameter is going to be weight well not parameter it's a variable and I know this can be slightly confusing cuz we have two variables referring to the weight but now for this neighbor we want to Traverse the BFS from this node as well but only if it's not been visit so we say for neighbor not in visit if neighbor is not init then we can go ahead and append to the que this neighbor and the new weight how do we get the weight do we just add the weight of this node that's not enough cuz that's only the weight connecting A and B do we just add the W value nope that's only the multiplication of the nodes before we reached this node we actually want to multiply them together W * weight and we also before we forget want to make sure this node is marked visited so I believe that is the entire code let me go ahead and run this to make sure that it works okay it's always the simplest things you mess up on I think I forgot to add dict over here this is a default dict and also when I append to a list we're appending a pair but here I didn't really do that so I want to wrap this in a list and this one as well okay now let's run this to make sure that it works and as you can see yes it does and it's pretty efficient if you found this helpful please like And subscribe subscribe if you're preparing for coding interviews check out NE code. it has a ton of free resources to help you prepare thanks for watching and I'll see you soon