Course Schedule II - Topological Sort - Leetcode 210
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/course-s...
0:00 - Read the problem
2:25 - Drawing explanation
10:40 - Coding explanation
leetcode 210
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#graph #topological #python - Věda a technologie
🚀 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:)
Severely underrated! 😂
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
```
Thanks a lot dude. I was banging my head to understand these two problems. You made it simpler. Thanks!
can't u just return "seen" for course schedule 2?
Totally agree now that I am solving this after solving course schedule i
NeetCode is a national treasure. I'm gonna write a whole ass page thanking you if I can actually get hired when I graduate.
What is an ass page?
Did u get hired yet
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.
+1
+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
@@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
Keep it up dude! Your visual teaching is really helpful!
thanks for sharing your knowledge. Your work is very useful and valuable.
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!
You commented this to make me feel dumb or what?
Amazing . Simply amazing . Great explanation while writing code.
Thanks for the amazing explaining! Recommend watching it!
very clean code with great explanation
Wrote out a similar thing, but this is so much cleaner and easy to implement/understand. Thanks :)
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)
Exactly what i was thinking.
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?
@@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.
@@sayantankundu973 I've been learning all these algorithms from his videos, so your explanation really clears things up for me. Thanks!
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.
Thanks. You explained a difficult-to-explain problem very well.
Wow ! What's a solution 😍😍great coding keep it up
The best explanation so far
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!
This is so helpful thanks!
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!
Really, how could it be possible that you were once a NEET? You explain topological sort better than my university professor...
You're my saviour neetcode
Hi, Thanks for explaining all problems in detail. Your implementation is not really using topological sort algorithm right?
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.
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
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!!
czcams.com/video/fc3jifPi7Fc/video.html
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)
Thanks, that was really helpful
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.
Hey, do you have the code in your github ? thanks
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
Thank you!
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!
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
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
Thank you so much
Thanks a lot!!
Neetcode aka Neet aka N. E. E. T. aka Natural Excellent Ecstatic Typer has yet again typed out another nutty leetcode solution
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! 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 :)
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.
@@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
```
@@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.
@@taotao555Thanks for the explanation
@@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
Neetcode is a beast
I've struggled a lot with this
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%
Is there a reason why you have both visit and output? Only having output would work?
Awesome!
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?
Why is both "visit" and "output" required? One of them should be enough right?
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?
Help: looking for solution of leetcode 1203: sort-items-by-groups-respecting-dependencies
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
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`
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.
Because checking if element is in output LIST takes more time (O(N)) than checking visit SET (O(1)).
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.
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.
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?
@@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)
@@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.
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
Checking if something is in a list is O(n), checking if something is in a set is O(1).
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
felt the same way. but great stuff!
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.
This is hierarchical query in Oracle connect by prior. Trivial
instead of returning output, can't you just return visit as it'll contain the same thing?
No , the ordering would be different , when you return a set it returns a sorted list in python
Any way to reduce the space complexity of this and also course schedule 1 ?
I am very depressed about this "Medium" question. Even understand the idea, but I can not understand the code.
why do you need 2 sets? just use the output array as the 2nd set and it still works
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.
[1,0],[0,1] you have the dean sign off on course 0. Done
You forgot to remove crs from map, it would improve the efficiency.
Just realized, visited set can be replaced by output set.
thanks! Visit set and output look redundant to me.
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.
Set is O(1) @@nikhilgoyal007
I feel so fucking dumb bruh
maybe you are
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 :)
Thanks for this man. Had the same thing in mind.
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.
U a God
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.
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.
This is not top sort? This is a DFS on a graph?
@jyothi9082 Topological sort can be done using DFS, beginning from any node in a DAG. See algorithms section of Wikipedia article
if num_courses == 1:
return [0]
Very complicated solution. Far worse than khan algorithm
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)
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
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).
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)