Shortest Path with Alternating Colors - Leetcode 1129 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem shortest path with alternating colors we're given nodes in a directed graph So based on this example we could be given a graph like this where each node will be numbered from zero all the way up until n minus one so in this case we have 0 1 2 and the interesting thing here is that we actually have edges in this case that yes are directed but they also have another property which is the color of the edge now in this example we have two red edges and zero blue edges but I made it a little bit more interesting by adding both of the colored edges and all we really want to do is start at node zero and find the length of the shortest path from zero to every other node in the graph and then return that in an array called answer so at the 0th position of the array will have the shortest path length from zero up until 0 and then in the next position we'll have the length of the shortest path from zero to node one and then in the next spot we'll have the shortest path from zero to node two but it's even more interesting because it's not just the shortest path we need a shortest path with alternating colors so in this case it's a pretty simple example we have node zero there's only one path from zero to one and it just has a single edge so it doesn't matter what color this Edge is it could have been blue it could have been red it doesn't matter because we started at zero so technically this is an alternating Edge so the length of this path is just one that's what we would Mark for this position now the only path from zero to two is this other path of length two and lucky for us the colors are alternating we started with blue and then then had red we could have had the opposite where we started with red and then had blue it would make no difference as long as they are alternating so we'd say the shortest path length to reach this node is 2. now in the actual example this Edge was actually red in that case the answer for this path would have been the same the length is still one but for zero to reach 2 the colors are not alternating so we return a default value for this node as negative one because we couldn't find a valid alternating path to this node so as with most shortest path algorithms we are going to use a breath first search approach to this problem we only need to find the shortest paths starting at this node so it should be easy enough but there's just one catch that we have to worry about and that is making sure the paths are alternating so as long as we can satisfy that condition this problem shouldn't be too bad so can conceptually we can solve this problem in a pretty easy way that would be by running two breadth first searches on our graph starting at zero because we know we have to alternate Edge color we can start the breadth first search at this node where the first Edge color is going to be blue and then find all possible shortest paths to every other node now in this case every Edge coming out of zero is blue so that would be the only valid starting Edge color but maybe if this one was red then we could start by taking like the blue edge and then seeing what are the shortest paths we can get in that case which would be one for this guy and then from here we can't take this Edge because it's also blue so we would take this red Edge and then say okay the shortest length to this guy is two and then say for this guy we are allowed to take this blue edge so the shortest path to this is three and then we would start at this node now the first Edge color we're gonna take is red we're going to start with red and then we would not be able to take this Edge but now we can take this red one so now we get to this guy we say well we just found a path that's of length one and that's shorter than the value that we had here which is two so we found a new shortest path length this is going to be one now and then from here we can take this blue edge and then we'd say the shortest path to this guy is now two instead of three so that would be a pretty basic way to do this problem just a couple of breath first searches just change what our starting Edge color is and I'm going to be using this idea but I'm going to be doing like a slightly more concise version which is when we start here there's no restriction we can take blue or we can take red so we do both but now when we get to this guy we have to mark the edge color we took to get here was blue and we have to mark for here the edge color we took to get here was red because that informs us on what Edge color now we can take because maybe we reached this using a blue edge that would be impossible with this example but you can imagine that maybe there is like a blue edge coming into this so we have to keep track of what color Edge we took to get to this node and not only that but we have to try multiple possibilities we want the shortest path that gets us here given a red Edge and we want the shortest path that gets us here given a blue edge being its previous Edge because that will give us all possibilities and then from here we have all possibilities because in this case there's only a blue outgoing Edge but you can imagine that there could have been a red outgoing Edge as well so we want all possibilities and other than that it's just going to be a basic breadth first search where we ensure that the edge colors yes are alternating and we don't want to get stuck in Cycles in our graph either so yes we are going to have a visit hash set but this visit hash set will not just Mark a node once we're going to mark it two times one for each incoming Edge color because remember we want to have all possibilities so we can't say a node is visited unless we visited it with a red edge and a blue edge as long as both of those exist maybe they both don't exist but we want to get all possibilities and in this case since we're doing both of those breadth first searches simultaneously we kind of don't even need to take the minimum distance because we know that for any node the first time we see it it's going to be the minimum distance anyway because we're doing the red and blue edges simultaneously so in terms of time complexity it's just a breadth first search and even though we're doing it twice the time complexity is still going to be Big O of n multiplying n by any constant whether it's 2 or 10 or 100 doesn't make it difference it's still Big O of n time complexity we do have a visit hash set so we are going to need o of n extra memory so now let's code this up so while this problem isn't crazy hard there's going to be a lot of code let's start with our hash Maps because we want to convert the incoming list of red edges and blue edges into adjacency lists we're going to use a hash map for that the default value for each of these is going to be a list because now when we go ahead and get the source and destination node in let's say our red edges first we're going to say red for the source node we want to append to its adjacency list the destination node now if we key this but we haven't even inserted Source yet into this because this is a default dictionary with a default value of a list this won't throw any exceptions or anything and we're going to do the exact same thing with our blue edges because these are directed edges we we only have to add the one-way connection from source to destination let's change this to our blue hash map the names are not the best you can definitely change the names if you prefer I'd like to keep things concise for coding problems though coding interview problems now let's go ahead and initialize our answer array usually I call this result but in the context of this problem they call it answer so I'll do the same we want to initialize this initially with just a bunch of negative ones so for I and range for the number of nodes that we're given we're just going to put a negative one everywhere except we know the starting position is always going to be node 0 so we can say that the shortest path length from node 0 to itself is just zero now we're going to be doing a breadth first search so we want to have a deck so in Python a double-ended queue we can just initialize like this the first value we want to add to it is the node 0 but we also want to be able to keep track of its distance and the color that we took to get here which initially I'll just say is null so just to make things more clear the first value is the node the second value is the length and the third value is the previous Edge color this will make more sense as we actually go through the breadth first search but lastly before we start that we do want a visit hash set and initially We'll add to that our current node that we just had and we don't need to keep track of its length when we mark it visited so we'll just say zero is the node and it was visited with a none previous Edge color that's just null doesn't really matter in this case but the reason here I'm doing a tuple and here I'm doing a list is because with hash sets you have to add tuples you're not allowed to use arrays so now let's do the breadth first search so while our queue is non-empty we're going to be hopping left from the queue when we pop we get three values we get the node we get the length and we get the previous Edge color which I'm just going to call Edge color so we get these three values just like we added them up above now if this is the first time we're visiting this node how do we know that well in our answer array at the index of this node this will be equal to negative one just like we initialized it so if this is the case then we just found the shortest path length so here we'll say this is equal to the length that it took to get to this node because that's what we appended so for the first iteration of this loop we're going to pop the zeroth node and Mark its length as being zero so I guess up here we actually didn't even need to do anything so actually let's get rid of that line so now we want to start going through the neighbors of this node so what we could do is say the edge color is equal to Red then we're going to enter iterate through the blue neighbors if it's equal to Blue then we're going to iterate through the red neighbors but notice how initially the edge color is null so a better way to do this would be to say if the edge color is not equal to Red then we're gonna go through all the red Neighbors which we can do like this and in the opposite case if the edge color is not blue then we will go through all the blue neighbors like this the good thing about this is that on the first iteration of the loop this is null so in that case both of these are going to execute which is exactly what we want to happen we want to be able to go to the red and blue Neighbors on the first iteration of the loop but also if the color was red then we would only want to iterate through the blue neighbors and not the red numbers if the color was blue then we'd all only want to iterate through the red neighbors not the blue neighbors and that will also work in this case so to fill this out going through the red neighbors it's just going to be like a basic breadth first search where we want to check if this neighbor color combo which is red if this is not in visit then we can go ahead and add it to being visited and we can then add it to the queue we can append it to the queue which we want to add three values the node the length which is length plus one length is the previous length and we just want to add one to it now and the current color which is also red and then we want to fill out the rest of this basically I'm copy and pasting because it's going to be the same except the opposite so we're going to change all these Reds to being blues and I think that is pretty much it because we can visit the same node multiple times as long as we had a different incoming Edge because we don't know which one of these paths is going to lead to us finding a different shortest path to other nodes so we have to take both of these paths and that's pretty much it for our breadth first search when we're done what we want to do is return the entire answer array which is where we stored all the shortest paths so that's 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