Course Schedule II - Topological Sort - Leetcode 210

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@madhumithakolkar_]

The [[1,0],[0,1]] situation reminds me of how companies ask for prior experience to get a job, and for prior experience you need a job in the first place:)

[@ShivanshThapliyal]

Severely underrated! 😂

[@caterpie-]

same here

[@totoshi27]

catch 22

[@tenkara101]

Don't get me wrong- Neetcode is still an invaluable resource but i think the course schedule problems would have benefited a lot if both videos used the same pattern/template and variable names. `cycle` in course schedule ii is basically the `visiting` set in course schedule i. should have been both `cycle` so it's easier to understand the purpose of those sets. they're just to detect cycles. while `visit` or `seen` denotes this is a node you've processed, no need to do it again. it's more a way to `break` the loop if the graph happens to be cyclic. course schedule i and ii are the same problem with 2 line changes if you use the pattern for these problems. my pattern: ``` def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: adj = {} for i in range(numCourses): adj[i] = [] for a,b in prerequisites: adj[a].append(b) // for course schedule ii // res = [] cycle = set() seen = set() def dfs(cur): if cur in cycle: return False if cur in seen: return True cycle.add(cur) for child in adj[cur]: if not dfs(child): return False cycle.remove(cur) seen.add(cur) // for course schedule ii // res.append(cur) return True for i in range(numCourses): if not dfs(i): return False // return [] return True // return res ```

[@bhargavacharan2262]

Thanks a lot dude. I was banging my head to understand these two problems. You made it simpler. Thanks!

[@TusharSharma-nt7hg]

can't u just return "seen" for course schedule 2?

[@selfhelpguy5589]

Totally agree now that I am solving this after solving course schedule i

[@moveonvillain1080]

Well in cs-i the seen part was covered by making the value for that crs as an empty array after we have gone through the prerequisites.

[@mickeycoreight7481]

yep I agree, thanks for the code

[@expansivegymnast1020]

NeetCode is a national treasure. I'm gonna write a whole ass page thanking you if I can actually get hired when I graduate.

[@PorkBoy69]

What is an ass page?

[@Hoduekim]

Did u get hired yet

[@atrivyas8512]

@@Hoduekim yes, we just finished flipping burgers for today

[@Hoduekim]

@@atrivyas8512 i dont know whether to laugh or sob

[@RolopIsHere]

@@Hoduekim A good offer from Amazon, delivering packages.

[@slayerzerg]

This is much better description than the Course Schedule I video code-wise. I could tell you were doing topological sort in that previous question 207, which does consist of DFS. Great job you explained it so clearly here.

[@nehaa3778]

+1

[@alibaba888]

+1 - `if dfs(res) == False:` is much intuitive and natural in English than `if not dfs(res) == False: return False`) - using a different set to track visited instead of setting it to `[]` is much more natural to read

[@yiqin6863]

@@alibaba888 I am using the solution in LC207, and set maps[crs] to '[]' as the visited condition, but it seems wrong, not sure what happened

[@rahul911017]

For people who want to learn Course Schedule I on the lines of this concept discussed here: class Solution { HashMap prereq = new HashMap(); // hashset to mark the visited elements in a path HashSet completed = new HashSet(); // we use a hashset for current path as it enables quicker lookup // we could use the output to see if the node is already a part of output, // but the lookup on a list is O(n) HashSet currPath = new HashSet(); public boolean canFinish(int numCourses, int[][] prerequisites) { // base case if (numCourses

[@raevenbauto1578]

Keep it up dude! Your visual teaching is really helpful!

[@MrEdgoll]

thanks for sharing your knowledge. Your work is very useful and valuable.

[@DmitriyKl]

I'm super excited that I came up with this solution on my own after solving Course Schedule I! I actually thought my solution was hacky because I'm using a set to keep track of known courses we can definitely take (for constant time lookup) and a list to store the result to maintain course ordering. Glad to see my solution was very close to yours!

[@therishabhdhiman]

You commented this to make me feel dumb or what?

[@parmanandabanakar3713]

Pictorial representation of course dependencies should have been opposite. Then, the result would have been in reverse. Nothing wrong, Just a different interpretation of topological sort. Great Job (y)

[@sayantankundu973]

Exactly what i was thinking.

[@PippyPappyPatterson]

I have TS down pretty well, but the direction of the graph's edges vs node-dependency is tripping me up. Can you talk about how you think about graphs of real-world dependencies? Should an edge `u, v` represent `u only if v` or should it represent `if u then v`? I.e. is it conventional to have an edge represent that a vertex is dependent upon its subvertex, or should an edge represent that a subvertex is dependent on its vertex?

[@sayantankundu973]

@@PippyPappyPatterson If there is an edge from u to v, i.e. u - > v ... It means, while traversing the graph, 'u' comes before 'v' ... So, we have to visit 'u' BEFORE visiting 'v'... Same thing with respect to courses... If there is an edge 'u' - > 'v' , we have to complete course 'u' before completing course 'v', hence 'u' is a pre-requisite course of course 'v' This is exactly opposite of what the order is given in the video.

[@PippyPappyPatterson]

@@sayantankundu973 I've been learning all these algorithms from his videos, so your explanation really clears things up for me. Thanks!

[@freindimania11]

Fried my brain too. The video has the opposite representation of the formal definition `every directed edge uv from vertex u to vertex v, u comes before v in the ordering`. I don't think we can even apply Kahn's Algo to find the topological sort with this. Edit: we can apply Kahn's - have to reverse the logic to consider outdegree instead of indegree.

[@tanishbansal1058]

The reason to use two sets: the first (visit set) checks if any node has been visited in different DFS branches, and the second (cycle set) checks if any node has been visited in the current DFS branch. If you have a node that is visited again in the current DFS branch, it means you have a cycle. If we just empty the list after we're done with a node, we will lose that node's information down the road. This is problematic because we might need to visit this node from a different DFS branch in the future.

[@minciNashu]

So in Course Schedule 1, the condition to return True and skip DFS was an empty prereqs list. But here the condition is a secondary visited set. I think they both can be solved with just one visited dict (not set). So besides the return types, these two problems don't seem that different. class Solution: def canFinish(self, vertices: int, edges: List[List[int]]) -> bool: graph = {v: [] for v in range(vertices)} for v, nbr in edges: graph[v].append(nbr) # res = [] # CS2 path = dict[int, bool]() def dfs(v) -> bool: if v in path: return not path[v] # notice the negation path[v] = True for nbr in graph[v]: if not dfs(nbr): return False path[v] = False # res.append(v) # CS2 return True for v in range(vertices): if not dfs(v): # return [] # CS2 return False # return res # CS2 return True

[@harrydalal2193]

Hey I was really curious which app do you use for recording these videos and for writing notes? Thank you for your videos, they are really helpful!!

[@rakeshkashyap84]

kzbin.info/www/bejne/nJSWm5ychc5qfMU

[@thepinkcodon]

Hi! I have a follow-up; Why can we not simply do with only the visit set? Like we did in Course Schedule I? (Why do we also need a cycle set?) PS: Thanks for your awesome videos :)

[@thepinkcodon]

Okay so I figured it out. If we do not keep a visit set, then every time we visit a particular course by dfs, its value will be appended to the output, which we do not want. For eg: Input: {0:[], 1:[0]} >> Here, the first time we do dfs(0), we append 0 to output, AND add it to the visit set. Now, when we do dfs(1), we end up visiting 0 again. >> However, this time, since 0 is already in the visit set, we DO NOT append it to the output. Rather, we simply return True for dfs(0). In this way, the visit set allows us to avoid writing a visited course multiple times to the output.

[@findingMyself.25yearsago]

@@thepinkcodon Actually we can have without cycle set, below is my code, i will check both visited and output before proceeding BFS ``` class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: preMap = { i:[] for i in range(numCourses)} #populate preMap adjacency matrix for course in prerequisites: preMap[course[0]].append(course[1]) #Order is going to be the final list of courses in order order = [] #If in adj. matrix there's no pre. for particular course, then add at begining for pre in preMap.keys(): if not preMap[pre]: order.append(pre) visited = set() def dfs(course): if course in order: return True #False means there's a loop if course in visited: return False visited.add(course) for pre in preMap[course]: if not dfs(pre): return False order.append(course) return True for i in range(numCourses): if len(order) != numCourses: # we strictly stop here, because if there's loop, we need to return [] if not dfs(i): return [] return order ```

[@taotao555]

@@thepinkcodon I think the naming here is a little bit different. So what I understood is that the cycle set in Course II is actually doing the same thing as visit set in Course I. And the visit set here is to be more efficient for the for loop later, so that we don't need to run dfs(I) again in the loop if we already ran it in the recursion. It's kinda like what coursemap[n]=[ ] is doing in his Course I video. It's for efficiency. Please comment if I am wrong.

[@littlelittlebing]

@@taotao555Thanks for the explanation

[@dingus2332]

@@thepinkcodon From what I understood Visit is used to track the visited node ,that have been checked and looped upon for cycle check , cycle is used to track a cycle starting from x node , that is done recursively

[@hp-qx7tf]

Is there a reason why you have both visit and output? Only having output would work?

[@yustdream0204]

very clean code with great explanation

[@tony7948]

To anyone curious, using a list the size of the number of course and marking it as 0,1,2 for unvisited visiting and visited, you can save on the memory usage by 80%

[@niteshmanem1997]

Neetcode aka Neet aka N. E. E. T. aka Natural Excellent Ecstatic Typer has yet again typed out another nutty leetcode solution

[@harishsn4866]

Your solutions are always a delight but I personally felt like indegree/outdegree method was kinda more simple. Nevertheless, looking forward to more of your videos. Commenting and liking to get more of your reccomendation.

[@bolinsun9565]

Really, how could it be possible that you were once a NEET? You explain topological sort better than my university professor...

[@Boldpluto]

Amazing . Simply amazing . Great explanation while writing code.

[@servantofthelord8147]

Tough problem, but very rewarding when you figure it out haha. Thanks for the guidance!

[@ronhu744]

Interesting, the only reason we are using a set instead of a list for "visited" is for time complexity. If we use a list instead of set in visited, we can eliminate the need for the output list and we can return the visit list however I saw the runtime was higher

[@ZongjunQi]

Good work! I have a question regarding graph visiting related to the backtracking part. I see sometimes inside the dfs function, you do "visit.remove", sometimes you don't. Would you please summarize when to do either way? Thank you!

[@edwinrosemond989]

I think he's looking to use a bit extra space to save on time. Checking if a course exists in the set Visit is faster (O(1) time) rather than checking if the course is in your output already, which would need to search the whole output array. Cycle set here is similar to the visit set in his previous videos where visit is only specific to each node we start traversing from. Here output and visit are the exact same except visited is not ordered (in python). Thanks for video! Neetcode Let me know if I'm completely off

[@Dhruvbala]

In place of the visit hashset, you could just set prereq[crs] = None whenever you've added it to the output list. Kind of like what you did for the other problem

[@bigrat5101]

after watching your videos, now i have problem understand others videos...they just can't explain things as well we you can from my side of perspective. thank you NC!

[@TheJOEsat93]

Wrote out a similar thing, but this is so much cleaner and easy to implement/understand. Thanks :)

[@jansiranis4480]

Hi, Thanks for explaining all problems in detail. Your implementation is not really using topological sort algorithm right?

[@Moe_Alwaeli]

Thanks for the amazing explaining! Recommend watching it!

[@sealovingsoura3036]

Wow ! What's a solution 😍😍great coding keep it up

[@QVL75]

Thanks. You explained a difficult-to-explain problem very well.

[@Sulerhy]

I am very depressed about this "Medium" question. Even understand the idea, but I can not understand the code.

[@alibagheri]

Thanks for the great explanation!

[@nataliagrigoryeva6615]

Great video, as always! This provided a clearer explanation compared to Course Schedule I for some reason for me. My only question is whether we really need both the output and visited variables, or could they be combined into one?

[@damianseals]

I would really like to know why the course schedule I solution (along with adding in the output list) doesn't work for this solution. I used the equivalent checks to the ones in this video and could not get it to work even though the logic is the same (i.e. instead of adding the course to the visit set at the end, I set preMap[crs] = [] like in the first video)

[@danielsun716]

one question, I noticed that there is no "preMap[crs] == [ ]" after adding crs in visitedSet as the solution of Course Schedule I. In stead, neetcode choose to use visit.add(crs). Also, when neetcode describe the solution, he did said make the prepare[crs] = [ ], but why I cannot see it in the solution code? I have a hard time on it. Can someone help me understand that? Thanks.

[@danielsun716]

I think I might got the point. We could not let the preMap[crs] == [ ] adapted in this question. Because if we do that, the last vertex gonna be deleted and the for loop gonna go on. So that we will never put the vertex we have found into the output list. Am I right?

[@sihanzhu8447]

@@danielsun716 you can use preMap[crs] == [ ], the difference, just by adding the result immediately into the output list when you meet [ ] if PreMap[crs] == []: if cts not in output: output.append(crs)

[@itachid]

@@danielsun716 Yes, you are right. I used print statements in my code to verify the same. It appears that the code DOES indeed replace it with an empty array but in order to get around this, u do need to have another check as @Sihan Zhu has commented in addition to appending the course after running through all the prerequisite courses.

[@nepatriots11]

Great video... but why do we need a 'visit' list?.. We have 'cycle' to check whether the current flow as a cycle and we have 'output' to check whether we have already completed the course.

[@xinwilson]

Because checking if element is in output LIST takes more time (O(N)) than checking visit SET (O(1)).

[@SOMESHKHANDELIA]

Why is both "visit" and "output" required? One of them should be enough right?

[@taotao555]

This is an amazing videl. Thanks for doing this. I just have a question about one code line, why do we have to remove the crs from the cycle? I comment out that line, and it still works. Also wrote down each recursion step with some example cases by hand, I don't see whether or not remove crs from the cycle set affect the code. Is it because it's more efficient this way? Can someone help me to understand this? Thanks!

[@leonkarn652]

The best explanation so far

[@hwang1607]

Could you use a defaultdict(list)

[@incompetentdev5830]

You're my saviour neetcode

[@dataseance4041]

It may not be necessary to have both `visit` and `output` => both are "global" to dfs and carried through out the whole search process and both only record successfully taken courses. The solution works if we simply delete all lines with `visit`

[@mahadihassan5897]

why we cant use visited and output as same variable? in the loop we are adding/appending the course in visited and output. So why not a single variable?

[@halahmilksheikh]

I would do the opposite, apply this technique to Course Schedule I. Basically two problems for 1 algorithm. The neetcode did 1 was really confusing.

[@yumindev]

Hey, do you have the code in your github ? thanks

[@krishnakeshav23]

line 17 : if crs is in ouput, it means that it has been visited because that's what we doing in line 25, 26, so can we use `crs in output` instead?

[@begula_chan]

Thanks, that was really helpful

[@alright8255]

why do you need 2 sets? just use the output array as the 2nd set and it still works

[@anhngo581]

I think because a set doesn't have an order to it. Additionally, if we use a list to check if a value exists, it takes longer: O(n) vs O(1) if we use a set.

[@anshikgupta2993]

Hey great explanation but we are using hashmap with extra sets, doesn't it affects the space complexity a lot and can you please discuss the space complexity of this solution.

[@DeGoya]

I've struggled a lot with this

[@indranilchakraborty4965]

one suggestion, if you could link course schedule II and II code that would be very helpful. In course I you emptied that all prerequisite visited node. But in that course II it did not happen. BTW great video

[@dpynsnyl]

felt the same way. but great stuff!

[@TheMatttm]

I don't get it, the algorithm I understand, but wouldn't 4 and 5 need tp be in the beginning of output because they're entry nodes? output looks backwards to me edit: I did have to reverse the output in my java sln

[@goldengirlgains]

This is so helpful thanks!

[@jessanraj9086]

Thank you so much

[@DrOvenProofStorm]

Hey I just wanted to let you know that your explanation of this problem doesn't match the question, I can explain. It mainly involves how prerequisites are loaded into the hash map. in your explanation you have the hashmap as follows: { 0: [1, 2], 1: [3], 2: [], 3: [2], 4: [0], 5: [0] } this shows each course and what is required to take it (this is how its setup in course schedule 1). however, "course schedule 2" has the input for the prerequisites list setup differently. it has each course and then its requirements. Here is the difference in the inputs(it's stupid that they do this) COURSE SCHEDULE 1 input: [course, what it points to] COURSE SCHEDULE 2 input: [course, what points to it] the hash map will look something like this: { 0: [5, 4], 1: [0], 2: [3, 0], 3: [1], 4: [], 5: [] } hope this helps explain a little better as I was kinda stumped understanding :)

[@vishwaskhurana1217]

Thanks for this man. Had the same thing in mind.

[@varunshrivastava2706]

Hey I don't know whether they have changed the question its been 7 months but now the input is similar to course schedule I.

[@jaddy4387]

instead of returning output, can't you just return visit as it'll contain the same thing?

[@dingus2332]

No , the ordering would be different , when you return a set it returns a sorted list in python

[@phanidatta1994]

I see that both visit set and output list have the same contents. So, what is the rationale behind maintaining both list and a set ? Could anyone explain ? Thanks

[@emma.tuebingen]

Checking if something is in a list is O(n), checking if something is in a set is O(1).

[@qojte]

I feel so fucking dumb bruh

[@farazahmed7]

maybe you are

[@cocodinary]

Help: looking for solution of leetcode 1203: sort-items-by-groups-respecting-dependencies

[@iamsmitthakkar]

If you have followed the solution of Course Schedule 1, you can solve this problem with that almost exact same code. Refer below: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: preMap = {i:[] for i in range(numCourses)} visit = set() res = [] for p1, p2 in prerequisites: preMap[p1].append(p2) def dfs(course): if course in visit: return False if preMap[course] == []: # we need this to avoid duplicates if course not in res: res.append(course) return True visit.add(course) for pre in preMap[course]: if not dfs(pre): return False res.append(course) preMap[course] = [] visit.remove(course) return True for c in range(numCourses): if not dfs(c): return [] return list(res)

[@kuldeepchouhan8467]

Thanks a lot!!

[@santiagolimas2014]

Thank you!

[@34owner34]

Neetcode is a beast

[@nikhilgoyal007]

thanks! Visit set and output look redundant to me.

[@nikhilgoyal007]

My notes - cycle set = visiting; visit set = visited; output same as visited set here; (note cycle set before recursive call and removal after successfully returned). then add to visited.

[@shalsteven]

Set is O(1) ​@@nikhilgoyal007

[@jkrigelman]

[1,0],[0,1] you have the dean sign off on course 0. Done

[@zhangxinhello]

Nice job. We don't need cycle set. WE can check the node adj len .Let me explain why: if we re-visit a node, but the node adj is not empty, which means the node is in the cycle.

[@jaisinghbishtIN]

You forgot to remove crs from map, it would improve the efficiency.

[@jyothi9082]

This is not top sort? This is a DFS on a graph?

[@The6thProgrammer]

@jyothi9082 Topological sort can be done using DFS, beginning from any node in a DAG. See algorithms section of Wikipedia article

[@deepakumari1858]

Any way to reduce the space complexity of this and also course schedule 1 ?

[@Grawlix99]

You don't have to remove nodes from either the 'cycle' or 'visit' set, since there are two cases: 1. A node is part of a cycle and will be detected -> the DFS function returns False. 2. A node is not part of a cycle and is added to the 'visit' set -> the DFS function returns True. The point is, once you've added those nodes to the set, the DFS will reach a terminal state for those nodes, whether it's True or False. As a result, we never need to remove nodes from the sets, since we will never need to check their validity/invalidity more than once.

[@johnalvinm]

Just realized, visited set can be replaced by output set.

[@senthilkumar5]

Awesome!

[@amynguy]

kahn algorithm

[@edwardteach2]

U a God

[@testf5020]

Very complicated solution. Far worse than khan algorithm

[@findingMyself.25yearsago]

I tried without using Cycle set ( Only visited and output) class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: preMap = { i:[] for i in range(numCourses)} #populate preMap adjacency matrix for course in prerequisites: preMap[course[0]].append(course[1]) #Order is going to be the final list of courses in order order = [] #If in adj. matrix there's no pre. for particular course, then add at begining for pre in preMap.keys(): if not preMap[pre]: order.append(pre) visited = set() def dfs(course): if course in order: return True #False means there's a loop if course in visited: return False visited.add(course) for pre in preMap[course]: if not dfs(pre): return False order.append(course) return True for i in range(numCourses): if len(order) != numCourses: # we strictly stop here, because if there's loop, we need to return [] if not dfs(i): return [] return order

[@TKNinja007]

All you did was change the name of cycle set to visited. You're also using the output list as the visited set now which is inefficient (checking for an item in a list vs a set).

[@chethansaikrishna8401]

If same approach of Course Schedule I with minimal changes to be followed. Even this works ?!😅 def dfs(g): if g in visit: answer.clear() return False if len(graph[g]) == 0: if g not in answer: answer.append(g) return True visit.add(g) for j in graph[g]: if(not dfs(j)): return False visit.remove(g) if g not in answer: answer.append(g) graph[g] = [] return True def ans(): for f, t in e: if f not in graph: graph[f] = [] if t not in graph: graph[t] = [] graph[f].append(t) for g in graph: if(not dfs(g)): return False return True answer = [] visit =set() e = [[5,0],[4,0],[0,1],[0,2],[1,3],[3,2]] # e = [[3,1],[3,2],[1,0],[2,0]] # e = [[1,0],[0,1]] #prepare graph graph = {} print(answer)