Shortest Distance After Road Addition Queries I - Leetcode 3243 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem shortest distance after Road editions query the idea is that we are actually given sort of this representation of a graph well minus this Edge you have to think of it as a directed graph that's what unidirectional means in this context we're given n nodes that's going to be a parameter if it's five that means we're given nodes from zero all the way up until four and for each node like zero is going to point to one it's going to have a directed Edge to one one is going to have a directed Edge to two and it's going to keep going like that until we get to the last node which is not going to have like an outgoing Edge we're also given a list of queries which each of these actually represents a directed Edge so this means that there's going to be a new Edge introduced from two all the way to four what we want to do is return an array the same size as the queries array so we have three pairs here like three edges so we want to return an array with three values what those values are going to represent is after the introduction of this Edge what is the length of the shortest path from the zeroth node to the N minus one node we already know originally without the introduction of that it's going to be uh pretty much n minus one so we have five nodes that means we had four edges and so it takes four you know jumps to get to the last node but now with the introduction of the new one what is the new shortest path in this case it happens to be 1 2 and then three and now after we answer that query we're going to put three in the first position okay now we add this Edge as well so now the graph is going to look like this down here conveniently they gave us these pictures so I don't even have to draw them but now with the introduction of this Edge what's the shortest distance to four well it's not going to be taking this path which takes two we could cover that with just one jump like that so that's one two so we'd put two in the next spot and then lastly we'd introduce this Edge from zero all the way to four so in that case it's just going to be one Edge and we would return one in the last position and then that's the entire output and then that's going to be over here basically I don't have to probably tell you that this is a graph problem if you don't know what graphs are then it's probably going to be difficult to solve this problem so this is a graph problem so it's probably going to require some graph algorithm the fact that we're finding the shortest distance is a pretty big giveaway that among graph algorithms there's two very popular ones DFS is probably the most popular and then second is a BFS it's the second most common BFS is generally more optimal for finding the shortest path now if you know that BFS can find the shortest path you'll be thinking well okay how can we fit that into this solution and the good thing is that actually even a Brute Force solution will work in fact I think the Brute Force solution is the optimal one one so that will work but what would a Brute Force solution look like in the context of this problem the size of the graph is going to be n that's how many nodes are in the graph and that's roughly how many edges are in the graph as well in the worst case though like the last graph it's going to be of size n + Q in terms of like the total number of nodes and edges so that's like the size of the graph so we could say that a graph traversal isn't going to be any worse than this n + Q so a Brute Force solution would involve running a BFS every time we update the graph and add a new Edge to the graph so how many times are we going to run the BFS well Q times so we'll have q multiplied by n + q and I'll briefly cover how like the BFS algorithm works but given how standard of an algorithm it is and how many times I've explained it before and also the fact that I think there's like a million resources on neod bio to learn it whether you want to do it like the free Way by going through some of these graph problems I believe walls and Gates might be one I think clone graph might be uh one in any case like there's multiple solutions to these problems more so I think the algorithms for beginner's course in the course if you head over to the adjacency list section you have this pretty long lesson here but you'll probably specifically be interested in not the DFS part but the BFS on an adjacency list and like there's some animations there's a lot of notes on here there's the code in several languages so I think that's also a valuable resource to learn BFS the idea of BFS is sort of like a level order traversal we'll go through every level so initially like with this graph the first level is zero uh so that's going to be in our Q that's the data structure used for BFS so then we're going to go through everything in the queue right now and go through all the neighbors of each node that we pop so zero only has one neighbor and we'll know that because we're going to convert the original graph into an adjacency list where we will map every node to a list of its neighbors zero will have one as a neighbor initially one will have um just two as a neighbor initially etc etc we know that we did introduce this new Edge so two will actually have two neighbors three and four so we'll have a mapping just assume that we have that but popping Q we'll now have the second level which is one and then popping one we'll get to the next level which is just two and then after popping two it actually has two neighbors three and four so now we'll be here once we pop uh the four we'll realize that we have reached the target cuz we are looking for the N minus one node but we want to know how many steps it took to reach this position so we will basically count 1 2 3 you could count that in several different ways I think the easiest way to reason about is when you add values to the Q rather than just adding a single value you can actually add a pair of values the first will indicate the node and the second will indicate the length that it took to reach that node so initially we'll actually have a pair which is 0 0 it took us zero steps to reach the zeroth node next we will add one and it took us one step to reach that how did we calculate the new length we just take the previous length and add one to it every single time so this is what the next level will be and then the next level will be 2 two and then the next level will be a 3 three as well as 43 so when we do pop this one we will get the node and see that it's equal to the Target and then length it took us was three it took us three steps so that's how we will get the result that's all for the intuition let's code this up now so I'm going to take full advantage of python in today's video and do a little bit of list comprehension we know that initially um we could do something like this like for I in range n and then we could say adjacency do append to it a list and all the neighbors of the I node are just going to be i+ one like this list contains all the neighbors of the I node and it's I + 1 we're doing them in order we're going from zero all the way to n minus one so we can just append to the list from left to right that works but if you want to be fancy like me and do a little list comprehension you can check out my python for coding interviews course which will have a bunch of interactive lessons to teach you all these like python tips and tricks it's basically just going to be like this we will rewrite that code that I had before like this for I in range n so we get a little oneliner going and then we will assume we have an algorithm which will give us the short shortest path we actually don't really need to pass in anything into this function I'll have access to the jcy list since it's declared right here at the same level I don't need to pass in a source node I could to make this more modular if I wanted to but our BFS which is the shortest path algorithm is always going to start at the zeroth node and the target is always going to be the N minus oneth node so it doesn't really matter in this case so I'll just write it like this and then down here I'm going to build that result array that's what I'm going to return I can build it like this going through every single query in the list of queries I know that each query is actually a pair of values a source destination pair because the edges are directed for this Source node I want to append to its list of neighbors this destination node and then I want to run the shortest path algorithm and then the result of that is going to give me the length from zero to the N minus one node and then that length I want to append to the result now so that's literally the entire code you can see that most of the code is going to be in the BFS so I guess I was wrong it's not literally the entire code but I hope you understand what I mean so in here it's going to be pretty standard I've written this like a thousand times so I'm kind of on autopilot here but we're going to have a deck I'm going to initialize the deck by appending the first pair 0 0 don't forget that these represent the node and the length it took to reach that node and then I'm going to say while my Q is nonempty I'm going to pop from the que from the left side of it and I'm going to get two values the current node and the length it took to reach the current node before we go through the neighbors of the current node let's just check have we actually reached the target n minus one if so just return the length if not go through every neighbor in the current nodes list of neighbors so just like this and go ahead and append the neighbor so we will add a tupal here the first will be the node itself which is the neighbor and the second will be the length what is the length going to be to reach this node well if it took us this much to reach the current node it's going to take us one more Edge traversal to reach this node so we can say length + one now there's actually one little thing that we're missing we can't necessarily make any assumptions about the way the graph looks because even though it's started as an a cyclical graph after adding some queries we might end up with a cycle and that's not what we want to do so we don't want to visit the same node multiple times we only want to know what the shortest path it was to reach a certain node we don't need every single path we don't need to get stuck in like an infinite Loop so we will to mitigate against that declare a data structure up above I'm going to call it visit it's going to be specifically a hash set and so when I have a node over here before I append it to the queue I just want to make sure it hasn't been visited so if a neighbor is not in visit then I'm going to pend it to the que and I'm also at that point going to mark it as visited we're almost done now we don't need a return statement down here because we're guaranteed to reach uh the target position we know that there's always at least one valid path to it uh but one thing is we are saying that we're going to Mark a node visited once it's been added to the queue not necessarily when it's been popped because we never want to add the same node multiple times we never want to end up popping the same node multiple times so by the time that I add the node to the que here the zeroth node I should probably also Market visited just to be consistent so I will do this it won't work if you do not have this at least there are some edge cases that won't work there's the entire code let's give it a run and of course I had a very sloppy bug forgot one of the key words in uh but now you can see that this solution works and it's pretty efficient if you found this helpful check out NE code. for a lot more thanks for watching and I'll see you soon