Course Schedule IV - Leetcode 1462 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem course schedule four we're given a total number of courses let's say that's n then those courses are going to be numbered from 0 to n minus one this is a pretty standard way of representing a graph so these are going to be our nodes in the graph and we're also given a list of prerequisites which are going to describe the edges of the graph so if we have a prerequisite pair in our list of edges Like A and B this basically means that a is going to be a prerequisite of course B so to take course B we have to take course a first so it's going to be our job on how we want to represent the graph using these edges but I'll just tell you right now we're going to represent it like this by saying B is the course and a is the prerequisite then there's going to be an edge from B 2A so for a we're going to represent it like this we could do it the other way but I'm not going to choose to do that I think it's more simple to do it this way so for B A is its prerequisite because there's an edge going from B to a now there's also this concept of indirect prerequisites for example if a had a prerequisite maybe it's course C then it looks like this well C is a prerequisite of a so before we can take course a we have to take course C and A is a prerequisite of course B but also B has an indirect prerequisite before we can take course B we not only have to take course a but we have to take course C that's pretty logical and it makes sense but it's going to be important for this problem because what we're trying to answer here is given a list of queries so a query is going to look like this u v it's a pair of two nodes we want to know is this course the first one you do is this a prerequisite of the second course over here if yes we're gonna put true in this position if false then we're gonna put false in this position and by position I mean in the same position that the query is given because given a list of queries we want to return a list of answers so that's what we're going to be building that's the entire problem now how exactly can we solve it it can get kind of tricky especially if you want to be efficient so let's try to see what our options are so let's take this example and quick clarification we are told that our graph is never going to create or contain Cycles so that's good because if we had a cycle it would be pretty hard to answer any of the queries because it would kind of be true for all of them in that cycle but we don't have to worry about that so given a graph like this one how can we answer this question first of all let's say we're given a query like a B so we want to know is a a prerequisite of B well the simplest thing to do would be to start at B and then run a depth first search and see if we ever find a b or rather an A in our graph by running a DFS well we're going to go and visit here then from here we're going to visit these two guys and then from there we can't really go any further we didn't find a yet so we're going to pop back here and then try going down this way there's an F here well we couldn't find a so we'd put a false in this position that's easy enough and we could do this for every single query that we are given in the input now the time complexity of this is going to be the number of queries let's say that is Q times the number of prerequisites which let's say that is p so this is going to be the overall time complexity Q times p in that case p is really just the number of edges in our graph so actually if we wanted to be more accurate with this this time Galaxy we'd say it's p plus n let's say where this is the number of edges plus nodes in our graph so the size of our graph multiplied by the number of queries this is pretty good but actually we can get a bit more efficient than this I'll show you how what we're mainly going to do is we're going to have to run a DFS on the graph but we're only going to have to do it once the way I'm doing it right now we'll have to go through every node run the DFS potentially visiting the entire graph and then maybe you have to run a DFS from here potentially visiting the entire graph maybe run it here and we'll have to do that for every single possible node but not just for every node but for every query so we're really not getting rid of repeated work here I'm gonna do it in such a way where we only have to visit each node once but we'll also have to visit every Edge once so what the time complexity in that case is going to be P plus n this is the size of our graph we're gonna have to visit the entire graph but we're going to add a plus here because we're not going to do it so many times times and then here to actually answer every single query we're going to do that after we're going to first visit the entire graph populating the prerequisites the indirect prerequisites for every single node and then once we've done that with a single DFS then we're going to actually start answering the queries here which we're gonna do in this time complexity Q that's how many queries we have and then to answer each query is going to be a constant time operation so this is going to be Q times 1. now there's one last catch here it's actually not going to be this efficient because the DFS that we do is not going to be a really straightforward one we're actually going to have to multiply this by n which still is not bad when you think about it the size of the graph times n plus Q is most likely going to be better than what we originally had which I think was Q times P because n is actually going to be less than or equal to a hundred but Q could be up to a hundred squared same with p e could be up to a hundred squared which is the number of nodes that kind of explains why this is more efficient but now let's actually get the solution that will have this time complexity it's not super crazy actually it's very similar to the previous one so let's say we started our DFS at a then what we would do is try to build a hash map such that the hash map will map every single node for example a to a list or in our case we're going to use a hash set of all the indirect prerequisites of a and we're going to do this for every single node so for B we're going to do the same thing we're going to create a hash set same thing for c for all of them because once we have all of those indirect prerequisites it'll be very easy to answer any of the queries we'll be able to do it in constant time that's what we're trying to do we're going to start DFS here then recursively we're going to go to all of its descendants we're going to go to C okay while we're here we might as well find all of the indirect dependencies of C or indirect prerequisites so for C let's find all of its indirect prerequisites well we're going to go to D for D let's find all of its indirect prerequisites well it doesn't have any so for this one we'll just have an empty set and then we've gotten that for D and for E we'll also have the same thing e does not have any prerequisites so we'll have an empty set for e but what we're going to end up returning from these two notes up to the parent in a sense from D to C we're going to return what are all the nodes here we're going to return just the node D up to C and then from E we're going to return just itself up to our parent and then C is going to say all of my descendants are these two nodes D and E so these are the indirect prerequisites of C well I guess in our case they are direct prerequisites but we want all of the prerequisites the direct and indirect so now these are the prerequisites of C but what we're going to return to our parent a is going to be D and E and the node here itself which is C so these are the three nodes we're going to return to the parent here a now a is in direct prerequisites are going to be these three nodes and a would return up to its parent but it doesn't really have one we ran a single DFS starting from a but not only did we find the indirect prerequisites of a we did so for c d and e now what we're going to do is basically run this DFS starting from every single node so now we'd go back to C and try running the DFS here but what we would find is we already ran DFS from here we don't need to do that again same for D same for E we don't need to repeat any work so then maybe we'd try running DFS from B so doing the same thing we'd go to see our first neighbor and then find all the prerequisites here but again we already did that work it's already stored in our hash map so instead of repeating all of that work we would just return the same set that we have already stored in our hash map so these three nodes are indirect dependencies of B and then from here we'd go to our another neighbor f f doesn't have any dependencies or prerequisites but from F we'd return up to B the node itself which is f so now it'll take all of these nodes that were part of its indirect dependencies and add F to them so it's that simple then we would maybe try running DFS from F but we don't need to we already did that so we've done so for every single node here we have all of the indirect dependencies of every single node now it'll be trivial to answer all of these queries lastly how am I getting the time complexity for this I told you it was n the number of nodes times the time complexity to run DFS on this entire graph which is p plus n where p is the number of edges or maybe a better way to do this would be just e plus n because that's pretty obviously the number of edges and to make this even more simple we know that e the number of edges the upper Bound for that is going to be N squared because every single node could have up to n minus 1 edges coming out of it it could be connected to every other node that's like the upper bound so to reduce this we can actually get it to be n cubed but where do the terms actually come from for example where does N squared this is to actually go through the graph and then n here where does this extra n come from well remember from here we had returned a set of nodes which was this now from here we'll potentially get another set of no outs what's the upper Bound for the size of each of these well possibly up to n maybe it's n divided by 2 or something but it's still a factor or rather it's bounded by n this part down here is also bounded by n so to take these sets and merge these sets or Union these sets is going to be Big O of N and clearly in the worst case at every node we're going to be getting two groups or maybe three groups of nodes and merging them together and the size of all those nodes is going to be bounded by o of n so that's where this is coming from we're having to merge sets merge hash sets so that's where the overall time complexity of n cubed comes from though there are other terms here as well plus I think Q was the one to answer all of the queries but I think this will mainly be bounded by this term so now let's code this up so the first thing I'm just going to talk over is we're going to need to build an adjacency list I think this is pretty straightforward we're curating a hash map where every course is going to be mapped to a list of its prerequisites and we're going through that pair of lists right here next I'm going to show you how we're actually going to use our DFS before we actually Define it so we're going to have I'll call this prerequisite map where we're going to be creating a dictionary so I'll have to just create a basic dictionary here or you could call it a hash map we're going to map every course to a hash set of indirect prerequisites and then we're just going to go through every course in and we can do this in range of the number of courses because that's like the upper bound that we were given zero up till this number is all the courses and we're going to run DFS on that course and then this will populate our prereq map you can see right now it's just empty but running DFS will populate that and after that's done we're going to go through every query the way they defined it in the problem was UV is going to be how a query or those are going to be the names for the values in the query so I'm going to stick with that now using these we want to know is you a prerequisite of V so we're going to take our prereq map and we're going to use v as the key now this will give us a hash set of all the indirect dependencies or prerequisites of V If U is in this so if U is in this hash set then we want to append true to our results so let's actually Define our result here it's going to be an empty list so for every query we're either going to push true or false to the result this is going to be either a true or false value so we can actually just append this so result dot append this value is that query indirect prerequisite this is either going to be true or false that's the value we want to append here and then we can go ahead and return the result now before we do this we have to populate our prerequisite map so you can see how easy this problem would be if we had one of these now we just have to build it so we're going to define a DFS and we're going to do so inside of our parent function because then we don't have to pass every single one of these variables into our DFS but we will need to pass in the current course that we're at running our DFS on and if this course has already been visited how do we know if it's been visited well if the course is in our pre-rec map which is initially empty I'm actually going to do the opposite in this case I'm going to say if the course is not in the prerequisite map because if it's already in the prerequisite map then we're going to return the hash set that we already have stored in the prerequisite map which is going to be like this but if it's not already stored word then here we're going to do some different stuff we're gonna go through all of the direct prerequisites of this course so for prereq in the adjacency list that we built for this course we want to run DFS on that prerequisite what this is going to return to us is a hash set so before we do anything else let's for our prereq map for this current course let's at least put an empty hash set there now because this has been visited you could say so we'll put an empty hash set here now with this returned hash set we want to take every value here and also add it to this hash set we could do that with a loop but in Python it's even easier all we need to do is take this guy and set it or equal to this so this is like the union operator with hash sets we could write it out I think we could write it out like this or I'll just Ctrl z a couple times because I think it's more concise to write it the other way so I'll just stick to this but this is just the union of hash sets so after that's done we're going to return that hash set that we built but notice how we never added the original course to this hash set when we return up to our parent we want to include this current course not just the indirect prerequisites of this course but also this course itself so right before we return over here let's make sure we say prereq map dot add the current course as well and while adding to the course is a constant time operation this Union in the worst case won't be because depending on how many other courses we end up adding to this it's going to be an O of end time operation overall like including the entire loop as well but that's the entire code whoops I don't even know how I made that mistake so no we're not adding we're going to say for this course we're going to add to it this current course and another typo down here this is not prereq this is our prereq map sorry about that now let's run it and as you can see it works and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neatco.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon