Course Schedule II - Topological Sort - Leetcode 210 

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

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:)

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 ```

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

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.

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!

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

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)

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

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

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

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

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%

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

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.

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.

very clean code with great explanation

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

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

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!!

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

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!

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`

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 :)

Amazing . Simply amazing . Great explanation while writing code.

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

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

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!

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?

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?

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

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

This is hierarchical query in Oracle connect by prior. Trivial

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

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!

Thanks for the amazing explaining! Recommend watching it!

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.

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)

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

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.

I've struggled a lot with this

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?

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.

The best explanation so far

You're my saviour neetcode

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

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)

Thanks, that was really helpful

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 :)

Thank you so much

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.

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

I feel so fucking dumb bruh

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

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

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.

This is so helpful thanks!

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

Neetcode is a beast

Thanks a lot!!

Thank you!

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

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

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

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

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.

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

thanks! Visit set and output look redundant to me.

Awesome!

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

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

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

if num_courses == 1: return [0]

U a God

Very complicated solution. Far worse than khan algorithm

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

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)