Largest Color Value in a Directed Graph - Leetcode 1857 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem largest color value in a directed graph now while this is a hard problem whether you're a beginner or somebody who's been grinding a lot I'm going to show you some steps you can take to solve difficult problems like these and the most important thing especially with this problem is just reading the problem carefully I'm going to go through the prompt at least in a more simplified way because sometimes they try to confuse you with the prompt but the most important thing about this problem in my opinion is all the way at the bottom of the description which I'm not showing here but we're given a string of colors basically we're given a graph here every single node has some color associated with it now this is red this is blue this is purple that doesn't really matter because each color is going to be represented with a lowercase character that's right each color is going to be from lowercase A through Z that means that the number of colors is limited to 26. that's really one of the most important things about this problem that's what you have to catch but for the most part this is like most graph problems we're given a directed graph of n nodes in this case n is not going to be a parameter but we're also given a string called colors which represents the color of every single node so basically in that string the zeroth position might be lowercase a that maps to this node and the first position might be lowercase B that maps to this node so if we can just take the length of the colors array that will give us the number of nodes which is n in this case we're also given the list of edges they're directed there's something special about this but mainly we're going to use that to build our adjacency list because usually when you Traverse a graph you don't want to Traverse it using the list of edges the most common way that we Traverse things is using an adjacency list where we map every single node to its list of neighbors so in this case 0 has two neighbors that it can reach one and two they also describe to us what a path in a graph is as if we don't know that I don't know if they are trying to confuse us here or they just assume that we're stupid but yeah a path is just a path in the graph like this is a path meaning we go from zero to two to three to four we obviously can't go in the reverse order because the edges are directed and they're only going one way in this case now take this path as an example what's the most frequent color in this path well let's say this is a blue we have one blue but we have one two three red nodes so the most frequent color is red and the count of it is three so the only thing we're trying to do in this entire graph is find the path that maximizes the most frequent color so in this entire graph this is the path that maximizes the most frequent color which is red and the frequency is three and in this case that's what we want to return not the color not the length of the entire path or anything but the frequency of the most frequent color which in this case is three there's no path that we can make in this entire graph that will exceed that count now it's possible that a graph could have a cycle like what if we have a graph that looks like this well then we're just going to get stuck in an infinite Loop so they do tell us that in that case we can just go ahead and return negative one because we can't really find a valid path in that case so now we finally understand the problem which I think is the hardest part now I don't know about you but anytime I encounter a graph problem the first thing I try is the depth first search algorithm DFS because it's the most popular algorithm it's the most common so you definitely want to check is that going to lead us to a solution so let's try it out how could we apply depth first search to this problem well in the worst case we might have to look at every single path so how do we run DFS where do we even start it's not like they give us a starting point it's not like we can just start at node zero how do we know we start here why not start over here so I guess in the worst case we'd have to run DFS on every single node isn't that going to be really inefficient because running DFS might cost us the entire size of the graph so o of n let's say is the number of nodes well technically it would be n plus m m is the number of edges because we might have to Traverse the entire graph and how many times are we going to do this well maybe times n because we have to run it on every single starting point but is there something smarter that we can do here let's suppose I ran DFS starting from three I found out that starting from here this is the only path that we can really make so starting from three how many blue nodes were there along the path well there was just a single blue note how many red nodes were there well there was just a single red node so you're probably starting to get the idea if you have some experience with leak code problems where I'm going with this but I'll continue for now that was just the path starting at three now let's just say randomly we run DFS starting at two you might think now this DFS in the worst case is again now we might have to again Traverse the entire graph but two only has a single neighbor and it happens to be three so why should we now have to re-run DFS on this portion of the graph we don't need to we already have all that information stored over here so when I'm asking the question starting at two what's the maximum frequency of Blues that we can get what's the maximum frequency of Reds and we also have a third color here purple so I just add that right over here but it's obvious that I don't need to repeat all of this work so what can I do instead well I know that starting at two we do have a single red node so maybe I can just put a one here for now and then I go to my neighbor three I see it's already been visited I'm not gonna run DFS I'm just gonna look at Row three which is going to tell me what's the max frequency of Blues and reds so what I'm gonna do now is look at this position blue now so far let's just say we have zero because starting at two two does not have any blues we're gonna see that starting at three we can get a maximum of one blue so since this value is greater than this value we should take this value and move it over here we can uh get rid of this and now we have a one because we know going from two we can get to three and we know this path will have a single blue so that means starting from two there is a path that maximize the number of Blues and that path will lead us to a single blue and we're just gonna go column by column and do the exact same thing for every single color so here it's a little bit different though because we know two actually was the color red so here we're not going to take the maximum of these two values we would actually take this value and add it to the value over here so I'm going to get rid of this and add one to it so now we're going to have a 2 over here and we would do that column by column here they're just going to be zero so we don't really need to do anything but it's not entirely this simple because it's possible that two actually could have had additional neighbors going in other directions as well it doesn't in this case this graph is pretty simple but this could have been the case so what would we have done in that case well let's say another neighbor happened to be four like this neighbor over here is four so just to make it simple we have a four here there's some values here here x y z we don't care what they are but again we would go row by row we'd say let's look at these and since remember for every single node we're trying to maximize this position we're trying to find the maximum number of Blues the maximum number of red so what we would do as we go column by column comparing these two values we would take the maximum of both of them the only Edge case here is that on the source node which is two for the column where the source node is the actual color like in this case the source node was red here we would just want to add a plus one so we just have to keep track of that edge case we wouldn't just in this column we wouldn't just take the maximum of these two we would have to kind of consider a plus one but that's the only Edge case otherwise this isn't super crazy and you might think well for each iteration of the DFS if we're having to do these operations if we're having to go through this entire thing isn't that going to lead us us to a pretty inefficient solution not quite because remember what I said at the beginning the number of colors is bounded to lowercase a to lowercase C it's bounded to 26 colors maximum so it really isn't that bad and since we're never having to repeatedly visit the same node twice the overall time complexity of our DFS is just going to be the size of the graph n plus M well we do have a factor of 26 but that's a constant value we don't really care about that so this actually will lead us to the most optimal solution at least in terms of Big O time complexity I will mention there is a solution that will get you a better run time on leak code but this still will give you the Big O time complexity which usually is the most important for interviews so I think it's safe to stick with this simple approach and we didn't need anything super fancy all we needed was depth first search I didn't mention though there could be the possibility that we detect cycles and I'll basically talk about how we can do that within the code at a high level as we visit nodes like as we start at zero we go to two we go to three we go to four if we ended up coming back to the same node we'd want a way to track that I'm going to do that using a visit hash set well I think I'm going to call it something else because we're going to have visit to not repeatedly visit the same node twice but we're also going to have another hash set maybe I'm going to call it path to tell us what are the nodes in the current path of our recursive DFS like what are the nodes on the call stack of this DFS so now let's code this up so I'm going to start with just building the adjacency list this is not super complicated so I'm just going to have that here we're basically creating a hash map where the default value of the hashmap will be a list slash an array we're going to go through every Edge and we're going to map The Source node to the destination node we're also going to have a depth first search and what we want this DFS to do is given in some node as a parameter we want it to return the max frequency of the most frequent color so that's ultimately what we want this to do now I'm not going to fill it in yet because I usually think it's better to see how we can use it before so that's what I'm going to do we know we're going to go through every single node and try to run a DFS starting from that node well first of all how many nodes do we have well thankfully we can get that by taking the length of the colors array so then I can complete my for Loop for i n range n and then pass in that starting node into our DFS now what we're trying to do is maximize the result so I'm going to well first declare that variable result is initially let's just say is going to be set to zero that's usually a good default value and we want to maximize the results so we're always going to take the maximum of the result of this DFS and the maximum of the result and set it equal to the result now like I said we are going to need to keep track of which nodes have already been visited so that we don't do repeated work and we're also going to keep track of which nodes are in our current path of our current DFS like which nodes have been pushed onto the call stack because that will help us detect Cycles while it's required for us to detect Cycles so these are both going to be hash sets so we can do that just like this and this is kind of the complicated part I didn't explicitly talk about it but I kind of showed it with the picture we are going to have a two-dimensional grid which tells us the max count where we are mapping the count the node and the color to the max frequency of that color starting from this node so just like we talked about in the drawing explanation now to actually initialize this 2D grid well I'm going to do it the pretty much pythonic way you can do it however you would like but we know that every row is going to be the number of colors so the row is going to be 26 because we could have up to 26 colors so it's going to be an array with 26 zeros that's how you can do it in Python and how many rows are we going to have well one for every single color so I'm going to say for I in range n which we calculated up here so this is just a two-dimensional grid pretty much with these dimensions and this is going to be useful for us in our DFS now lastly I'm going to put our return result here we are going to modify this I'll mention that now but I'm going to save it until we finish up our DFS because remember we want to return negative one if we detect a cycle so we'll have to keep that in mind but now let's go on to the DFS there's a couple edge cases if the node is already been visited then we just want to return immediately I'll just return zero because it doesn't really matter there's also so the other Edge case if the node is in the current path then we want to indicate that we've detected a cycle so we have to return some special value here we could do negative one but the reason I'm gonna do something different I'm going to do flow Infinity basically like the maximum value that we can return the reason I'm doing this is it makes our code a bit more concise you can do it the negative one way but you'll find that you need like a couple extra lines of code doing it this way when we take the maximum because that's ultimately what we're trying to do we're trying to maximize this if we ever return Infinity from this DFS we're going to take the maximum and then our result will be infinity and once it's Infinity it can never become smaller than that so then by the time we get to this return statement we will be able to detect is the value Infinity if it is what we really want to return is negative one so I'm going to do exactly that return negative one if result is equal to float Infinity else return the real result whatever it happens to be it's it's probably zero or some positive value but it's not Infinity now one thing that you might not notice here is we kind of have a bug here because every time we get a node that's not been visited and is not in the current path what we're going to do then is add it to the visit hash set so we're going to say this node has been visited and this node now is in the current path so now if we visit that same node again then we're going to end up executing one of these but notice if the node is in the current path it's also been visited so if we get a node that's already been in the current path what we'd want to do is return Infinity to indicate we detected a cycle but that would never happen because we would always execute this one first so it's very important that you take this condition and have have it before this condition that's an easy way to have a bug so definitely something to keep in mind now for the kind of interesting part we want to take the count the maximum frequency color starting at this node and just set it and for the color of this node we want to set it equal to one because we know at the very least this node is some color and we can find that color and map it to one initially how do we get that color well that's where our colors string comes in we can take this node and map it to get the color of it but remember that string will return us a character what we want is an index so from lowercase A to Z we really want to map a to zero we want to map B to 1 and we want to map Z probably to 2 25 so how do we do this well I'm gonna do that like this I'm gonna basically call it the color index and I'm gonna get the ASCII value of that color basically mapping that color to some integer and subtracting the ASCII value of lowercase a so if the color of that node is lowercase a this will evaluate to zero if the color of that node is lowercase b this will evaluate to one so pretty much what we were looking for then I can use this color index to use it as an index of this two-dimensional array now finally we want to start going through the neighbors of our current node so we can get our adjacency list that's what we built this for and use the current node and get all of the neighbors of this node so while I haven't done anything super crazy you can see that this is quite a a lot of code it's a lot of things to keep track of it's really easy to make a bug here that's what makes this a hard problem in my opinion but for every node we just want to run a DFS on it now the only Edge case we have to worry about is what if it returns Infinity because if it does then we should probably just return Infinity right away and that's what we're going to do we're going to detect the return value of this is it equal to float Infinity if it is we're going to return float Infinity now I didn't store the return value in a variable because we actually don't need it in this case because whatever the DFS did the most important thing is that it populated our two-dimensional count array so we don't need the return value we just need the count array so now I'm finally going to do the thing that I talked about where we go column by column and how many columns do we have 26 one for each color so I'm going to say for C which basically stands for color or column whatever you think whatever you prefer I guess but there's going to be 26 of them so we're going to iterate 26 times we want to take the maximum of the count for the current node like the starting node which was the parameter of this function for the current color so this will give us that count and we want to maximize it with the neighbor so the neighbor here with the same exact color we want to find the maximum of these two values and we want to assign it to this position just like we talked about in the drawing explanation because right now we're considering this node as the starting point now the only Edge case is which again I mentioned in the drawing explanation is when we get to the color which is the same color as this color like as the same color as the starting node here in that case we would want to add a plus one we want to add a plus one to the neighbor's path because the neighbor has not considered this node yet so here we'd want to add a plus one what's the easiest way to do that well in my opinion to add like a ternary operator so here what I'm going to do is say this is going to be one if C is equal to color index otherwise it's going to be zero that's the most readable way in my opinion you can definitely try other things but I prefer this because we don't need to create more and more variables because the more variables you create the more names you have to create and in my opinion what makes code confusing to read is bad names and I'm pretty good at creating bad names so I try to minimize that now this Loop will find the maximum for every single color starting at this node and then that's what we want to return so starting at this node we want to find the maximum frequency of any color so we don't care which color we just want to find the maximum so this is an array we can just take the maximum of it and return that so then this method will do what we want it to do the only thing that you don't want to forget about is when you add a node to the current path right before you return you want to clean up you want to remove that same node from the current path we can do that just like this we don't need to remove that node from the visit hash set because we never want to visit the same node twice we also don't want to add the same node to pass twice but it's important for us to pop because then we can actually detect Cycles so that is pretty much the entire code it's quite a lot of it so hopefully I don't have any bugs let's run the code to confirm and as you can see it does work according to leak code's runtime it's not super efficient though the Big O time complexity is definitely optimal I can guarantee you that there just happens to be some other there just happens to be other solutions to this problem that happen to get a better run time on leak code but I don't think that's super important 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