Find Eventual Safe States - Leetcode 802 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find eventual safe States we're given a directed graph of n nodes where each node is labeled between 0 and N minus one now we're actually given the graph as a two-dimensional array so basically graph at index I will represent all the neighbors of the I node so for example if I equals z then we're getting all the neighbors of the zeroth node so essentially graph at index I is a list but remember that the edges are directed so what this means is uh let's take a look at the first example below at index zero we can see that this is the subl list that we have one and two means that from the zeroth node there is an edge going outward from zero to the first node and an edge going outward to the second node similarly the next one is two and three that means there's two edges going out from this node to two and to three we're also told that a terminal node is a node that does not have any outgoing edges so six of course is a terminal node there's no outgoing edges five is also a terminal node there are incoming edges to five but there are no outgoing edges same as four it's also a terminal node the rest of these are not terminal nodes you can see three has an edge going out two has an edge going out and you know the rest as well but we're not so interested in terminal nodes we're actually more interested in safe nodes and a safe node is defined as a node that if you took every possible path from uh this node every outgoing Edge and then just kept going eventually all of the paths would lead to terminal nodes now if you're clever what you're going to realize is that what all that really means is that there's no Cycles in the graph because think about it what if we didn't reach a terminal node how could that be possible well let's look at Zero from zero we can go to one from one we can go to three from three we end up back at zero so it doesn't even matter what the other paths from zero R because we found one path that will never lead to a terminal node but just to take a look let's see what would have happened if we took a different path suppose we got to one and instead of going to three let's say we went to two then two only has one other outgoing Edge which leads us to five five is a terminal node so we did find one path from zero that will lead to a terminal node but that doesn't mean zero is a safe node because one of the paths we saw earlier would lead to a cycle so zero is not a safe node but doing all of that did you notice by trying to figure out whether or not zero is a safe node we found out a few other things we found out that one is also not a safe node because one was a part of the original cycle that was from 0 to 1 to three back to zero so it was also part of the cycle so one is also not a safe node and we also found that two is a safe node because we went through all possible outgoing paths from two it only took us to five and then we couldn't do anything else so two is a safe node all the paths from two lead to a terminal node also of course we found out that five is a safe node because it is a terminal node why this isn't important is because we won't have to do a lot of repeated work because by asking the question whether or not zero is a safe node we found out that a bunch of nodes are or aren't safe nodes and we won't now have to revisit them this means we can do this algorithm in Big O in Big O of let's say e+ V time this is kind of a standard way to write it what this means is the time complexity will be the total number of edges in the graph plus the total number of vertices or nodes in the graph because we're going to do this recursively with a depth first search algorithm I mean how many ways are there to Traverse a graph usually DFS is the standard way so that's what we're going to do and using the reasoning that I talked about earlier we won't have to ever revisit a node or revisit an edge so that's why this will be the time complexity and that going to be about as good as you can get for this problem before we code it up let me just show you a couple techniques we're going to use to achieve this time complexity so we're going to use a hashmap to map each node to the status of whether it is a safe node or not and actually I don't think I even mentioned what we're going to return in this problem is going to be basically for every single node we want to know if it is safe or not and we want to return that in ascending order that's pretty straightforward it just means for every node that we have here it's going to be mapped to an array basically we just want to return a list of all of the safe nodes so if we can find out whether a node is safe or not then we will go ahead and add it to the output so since we want to return it in ascending order though we should probably go in ascending order we should ask is zero safe or not is one safe or not etc etc we'll build that mapping and at the same time we will build our output array but let me show you why this hashmap is going to be important to make this solution efficient so first we're going to have a four Loop going through 0 through 6 we're going to start at the first one and just like I showed earlier we're going to do a DFS on this so we're going to go to one of the outgoing nodes we get to one then from one we're going to go to another outgoing node we're going to get to two and then from two we're going to go to the only outgoing node we can get to which is five now we can't go anywhere else so what we determined is that five is a safe node so to remember that let's go ahead and add that to our hashmap so for five we're going to put true it is safe and then recursively we're going to end up getting back to two and what we're going to say is well all of the neighbors of two which only includes five all of its neighbors were safe so that must mean that two is also a safe node so we're going to add that to the hashmap as as well two is a safe node and then we're going to pop back to one one though we haven't visited all of its neighbors yet now we're going to go to three and then from three it only has one neighbor we're going to go back to zero at this point we're going to get stuck in an infinite Loop so there's multiple ways to get around this and what I'm going to do actually is as we first visited zero and then we visited one and two etc etc what we're going to first assume is those nodes are not safe nodes so initially we're going to add zero and one to uh the hashmap and we're going to say false that they are not safe we're not 100% sure yet but the reason we're doing this is if hypothetically we get to three then we add three and say it's also false and then we're going to from three get back to one of the original nodes that was on the same path and we're going to know we got to one of the original nodes because in the hash map the value false is going to be there so once we get to zero we know we've detected a cycle because zero is already in the hashmap as false so at this point we would return because we determined that three is not a safe node one is not a safe node and zero is not a safe node so at this point we would continue our for Loop we already determined the status of zero then we get to one well if you look at our hash map we already determined that status as well so we don't have to do we don't have to repeat all that work we did the same for two we did the same for three we didn't do four yet it's not in our hash map so let's do a DFS from four okay we're going to initially add this as a false because if for some reason you know along this Loop we ended up back at four then we would be able to detect that cycle but what we're going to find is that from four we get to five we already know that five is a safe Noe so therefore all the neighbors of four are safe nodes that must mean that four is also a safe node so we're going to pop back to four and we're going to take that false value that we had erase it and overwrite it with a true and then we're going to continue our for Loop we know that we just did four we're we already did five it's already in the hashmap now it's time to do six which is the simplest case it doesn't even have any outgoing edges therefore it is a safe node so you can see that we have the status of each of these it would be easy to convert this to a list like this one it's pretty easy to get the result you can see 2 4 5 six are all safe nodes that's exactly what they had in the solution as well so now let's code it up okay so now let's code it up the first thing I'm going to do is just get the length of the graph because we know we're going to have to iterate through 0 to n - one so getting the length is pretty straightforward we're going to have our hashmap of course we're going to call it safe and then we know eventually what we're going to do is a for loop we're going to go through every node in range n if this node is a safe node which we're going to determine from our DFS by passing in the I node we haven't written our DFS yet but if it is a safe node that's what our DFS is going to return is it a safe node if it is well we're going to have our result if I is a safe node we're going to add it to the result you can see that this of course is going to build it in ascending order because we're iterating through the nodes in ascending order so we don't have to worry about that after we've built it we're going to go ahead and return it so that's pretty straightforward now the only thing left is to actually write the DFS I usually like to write recursive functions inside of the outer function because then we don't have to pass in every parameter we don't have to pass in safe or the graph we only have to pass in I which is the node itself so I'm going to have I be a variable to eliminate repeated work what we're going to immediately ask is if I is in safe that means we have determined whether it's a safe node or not so let's just return that itself is I a safe node or not we know that's stored in our safe hashmap but if we don't know first we're going to assume that it is not a safe node because then we can detect Cycles then we're going to go through every single neighbor we can get the neighbors pretty easily because remember that was an input parameter we can get every neighbor of I by just taking a look at the graph now we want to know is the neighbor a safe graph or not so let's pass the neighbor into DFS so there's two cases one it's not a safe Noe if this if one of its neighbors is not a safe note Noe then that must mean that I is also not a safe node so in that case we can just immediately return the value that we assumed which was initially false so then we'll immediately return false to make it even more clear I'll literally you know write it but if it is a safe node that doesn't really change much because we still have to go through every neighbor and confirm that every neighbor is a safe node if every neighbor is a safe node then this return statement will never execute then we'll break out of the for Loop and once we've done that we know that this is a safe node so we can go ahead and write that we can assign it to be safe and then immediately return true I don't know what's more clear I think it'd probably be more clear if I returned the safe value itself in both cases so I'll do that but if you want to write it this way feel free to you know explicitly write the false and trues but that pretty much is the entire code let's run it to make sure that it works and as you can see on the left yes it does and it's very efficient so I really hope that this was helpful if it was please like And subscribe it really supports the channel a lot consider checking out my patreon if you'd like to further support the channel and hopefully I'll see you pretty soon thanks for watching