Destination City - Leetcode 1436 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem destination city we're given an array paths where each path is actually an edge at least in terms of graphs it is basically a direct connection from City a to City B which again we can just think of as nodes in our graph and our goal here is to return the destination city which we Define as the city that does not have any sort of outgoing Edge what makes this problem relatively easy is that our graph is actually going to be a pretty simple structure it's basically going to form a single line without any Loop and therefore we're going to be guaranteed to have a destination city so in reality this is a really simple graph it pretty much looks like a linked list to me and this question is really just asking us what is the last node in the linked list now of course the difficulty comes from the input that we're given like we're not given this in the format of a link list we're given the list of edges for example here on the left I'm actually going to take this example because it's relatively simple we have B connecting to C so we have something like this B goes to C we have d goes to B so we got this here and then we have C goes to a so with all those put together this this is what we end up with and of course what we want to return here is the last one now there are multiple ways that we could solve this problem intuitively it kind of makes sense to just build out the graph and then we can pretty much start from anywhere we could start at the beginning of the linked list or we could just start in the middle either way we're just going to keep traversing it until we get to the end and then just return what the last one is like that's a relatively simple way to do this an even easier way way is to note the last thing that they say here actually not there I think here the last city is the one that does not have any outgoing City from it so what we can actually do here is go through these list of edges and we can record every single City that does have an outgoing Edge because the first one is the source and the second one is the destination right like with BC here we had this Edge created so for every single one of these we can say Okay B has an outgoing Edge D has an outgoing Edge C also has an outgoing Edge and then the last one that we're left with here is a it did not have an outgoing Edge so that's the one we would return now in terms of code how do we implement this the easiest way at least in my opinion is to take all of these like the ones that do have outgoing edges throw them in a hash set because it's an efficient data structure and then what we would do is iterate over every city in the input and actually we don't have to iterate over every city because we already know like these first ones in each pair are not going to be the result so we really only have to iterate over the Second City in every pair and for every city the Second City in every pair we're going to check does c exist in the hash set yes it does does B exist in the hash set yes it does does a exist in the hash set no it does not what does that mean that means a does not have an outgoing Edge so of course a is the result a is the city without any outgoing path that's what we're told to return so that's what we do now every time we iterate over these like that's going to be o of N and for us to check for each city is it in the hash set that's constant time so it's going to be an O of n algorithm to do this second portion and to actually build the hash set itself that's also going to be o of n so the overall time complexity is going to be just Big O of n the space complexity as well is going to be B go of n of course because that's the size of the hash set by the way n in this case is just a number of pairs that were given in the input array now let's code this up so here I'm going to create a hash set I'm just going to call it s you can give it a better variable name if you'd like but it doesn't really matter in this case and what we're going to do is for every pair or path in the list of paths we want to add the source City to the set so we can do that very easily like this so now that's pretty much it we've initialized the hash set to the way we want it the second part is going to be once again iterating over every path in the list of paths and now we check if the Second City like the distination is not in the hash set then it must be the one that does not have an outgoing Edge and it must be the one that we should return and that's exactly what we do it's guaranteed that one is going to exist so we don't need to put another return statement out here so this is the entire code let's run it to make sure that it works and as you can see on the left guess it does and it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon