Find Closest Node to Given Two Nodes - Leetcode 2359 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find closest node to two given nodes we're given a directed graph of n nodes numbered from 0 to n minus one in this case though each node has at most one outgoing Edge though that's not really relevant to this problem I don't think it sort of is but even if it wasn't true the problem wouldn't really change too much the graph itself is represented with a list of edges now it's not a two-dimensional list of edges so the index is going to be the source node and the value at that index is going to be the destination node if there's no outgoing Edge from I then the value is -1 to indicate that there is no actual node for the destination we're also given two Source nodes sort of node one and node two and probably the hardest part of this problem is understanding this paragraph here cuz this entire problem isn't super difficult it's mainly just graph fundamentals once you actually understand what they're trying to ask which is we want to know all the nodes that we can reach starting from node one in this case node one is zero so from starting from here we want to know all the nodes that we can reach also starting from node two which in this case is one we want to know all nodes that we can reach starting from here in this case both of these nodes can reach the two nodes 2 and three written another way we know that starting from node zero we can reach node 2 just by moving moving along one Edge so this is the distance to reach node two we can also reach node three by moving along two edges and it's the exact same for node one in this case as well so I'll quickly write that now ultimately what we want to find is among all of the nodes that we can reach from both node zero and from both node one so in this case there's two possibilities there's node two and there's node three for each of those nodes we want to find the maximum distance from node zero and node one in this case it's one in both cases so to take the max of both of these is pretty easy it's just one and we want to do that for all of these so for node three as well what's the max distance well it's two in both cases so we just say two now among all of these values we want to find the closest node to both of these given nodes so what we would do with these is minimize this array of values of course the minimum in this case is one and what we want to return is not one itself cuz this is the distance we want to return the actual node that is the closest to both of these and that node is two we added it to both of these so at a high level that's pretty much the problem so if you were confused what it was asking that's what they mean when they say such that the maximum between the distance from node one to that node and from node two to that node is minimized that's what they mean they mean taking the maximum of these two values and doing that for every single node and then minimizing the actual distances and if no possible answer exists we would return -1 and when exactly would that occur well if possibly node zero can only reach node three and maybe node one can only reach node two then neither of these two nodes can reach the same node so we can't really do anything we can't do the minimum and maximums that we were doing previously so our result would just be a default value of -1 so that's what we're trying to do how exactly can we do it well one the way I'm writing this it kind of implies that we would probably want to use a hash map for node zero and for node one we want to map every node to the distance it is away from both node zero and node one so we're going to have two hash maps and to actually find these distances we'll just run a basic graph algorithm we could do either DFS or BFS and the reason they would be pretty much identical in this case is because each node has at most one outgoing Edge so BFS would pretty much run just like DFS in this case so you can pick your poison I'm going to go with BFS and we'll have to run it twice to build this hashmap and this hash map so you could say the overall time complexity we know BFS takes big go of n to run over a graph we'll have to do it twice so we say 2 * n but that reduces to Big O of N and to actually build these hashmaps it's going to take Big O of n memory as well so now let's code it up so since we're going to run a graph traversal the first thing we probably want to do is create a adjacency list since we're just given a list of edges we'll have to build that ourselves so I'm going to create a hashmap which in Python you can do like this default dick and we're going to be mapping every Source node to the list of nodes that it can reach so we're going to go through every node in our edges so in Python easy way to do that is enumerating the list of edges so we'll get the index and the value at that index which I should probably call something else I'll call it destination so then we're going to say that for this Source node I we're going to append to its adjacency list the destination node so it can reach that destination node and then we know we're going to run BFS but I'm not going to quite Define the entire function just yet we know that we want to create two hashmaps for the distance mapping every node in the graph to the distance it is away from node one and we want to do the exact same thing for node 2 so I'm just going to rename this and then we want to actually run our BFS we want to start from node one also passing in this node one distance map because we want it to get filled up after running our BFS and we're going to do the exact same thing whoops for node 2 and so now we can probably start filling in the BFS we know we're going to have some Source node and we're going to have some distance map let's call it that this is going to be a pretty cookie cutter BFS algorithm so we're going to create our q and python you can instantiate a deck we need to obviously have some Source node that we're going to start with of course that's our parameter source and we want to also give it a second value because we don't just want to run BFS we want to keep track of the distance for every single node that we have visited the source node we can say the distance it is away from itself is going to be zero I didn't quite mention this earlier but an edge case is that can the return value of this be one of the source nodes node one or node two themselves and the answer is yes in this problem so it's important that we do add this here it's also important so that we don't get stuck in an infinite Loop when we run our BFS next we're just going to continue iterating while our Q is nonempty so we're going to q.p left and when we pop we pop a node and we pop the distance that that node is away from the source and then for that node we want to go through all of its neighbors so for every neighbor in the adjacency list of the node that we just popped we then want to take this neighbor and append it to the Q and the distance that this new neighbor will be is the distance of the node that we just popped plus one of course because we're just you know traversing along another Edge so distance plus one and while we're at it we might as well fill in the distance of that node so we can say for this neighbor the distance is distance + one but remember we don't want to get stuck in an infinite Loop so we're only going to do this for every single neighbor that has not already been visited yet how do we know if a node has already been visited if it's been added to the distance map this distance map kind of serves two purposes to actually map the distance for every node and to make sure that every node has been visited so if neighbor is not in distance map then only then do we actually execute this which reminds me when we append this source to the Q we should probably also add its distance to the Q which is just going to be zero well not to the Q to the distance hashmap once we have that done it's a pretty straightforward algorithm if you can you know figure out what the problem is asking we know that the result should initially have a default value of NE -1 cuz that's supposed to be the default value and we also want to keep track of what the result distance is because we only want to update the result remember the result is the node itself not the distance we're not returning the minimum distance we're returning the node that has the minimum distance the result distance will initially set to Infinity because we're trying to minimize it so any value that's less than infinity is going to work so then we can just go through every single possible input node an easy way to do that is just take the length of the edges that we were given because we know every node is labeled from 0 to n minus1 and we know the number of edges is going to be the same as the number of nodes and then we want to check we want to make sure that node is in node one distance map and it's in node 2 distance map it can be reached by both nodes then we want to calculate the max distance that it is from from node one we can get the distance like this that's why we created these two hashmaps and same thing for node two we can get the distance like this we take the maximum of those two and that's our distance now only if our distance is less than our current result distance do we actually update the result and we would then update the result to I because we want to return the node itself not the distance but we do have to update the result distance just like this and then finally we can go ahead and return our result before I run this to make sure it works I want to quickly mention that here up above the way we created our adjacency list we know that some of the destination nodes could have been NE -1 and we added those to the adjacency list and we also traversed them over here and so in some cases we would have added a NE -1 as the key of our distance Maps but since the way we traversed the nodes here we only made sure to Traverse from 0 to n minus1 we will basically ignore those and it doesn't doesn't really change the overall time complexity either actually I just noticed a typo here this should be result distance not result D so 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're preparing for coding interviews check out NE code. it has a ton of free resources to help you prepare if this was helpful please like And subscribe thanks for watching and hopefully I'll see you pretty soon