think of a directed graph 0->1->2->3->4, isn't your solution's time complexity O(E * N**2)...you will start the same loop for 1, 2, 3, 4 after doing it for 0
@@jchakrab No. Both the visitSet and updating preMap[course] to empty will ensure that we no longer need to start the same loop when processing nodes that's already visited.
The .remove(crs) was so confusing but I finally understood it. Simplest explanation: if we exit the for-loop inside dfs, we know that crs is a good node without cycles. However, if it remained in the visited set, we could trip the first if-clause in the dfs function if we revisit it and return False. That's what we don't want to do, because we just calculated that crs has no cycles. So we remove it from visited so that other paths can successfully revisit it. Basically we can visit the node twice without it being a cycle due to it terminating multiple paths.
Actually you can see this trick in many graph, binary tree or other problems using back tracking. Because the visit set is only used to contain the current visit path. So whenever you exit the sub-function you create on this level, you have to pop the info you passed in before.
Pretty smart! He removes all pre-courses at once after iterate through one adjacency list. In the drawing solution, he removes the pre-courses one by one. To align with the codes, the list can only be "cleaned out" if all pre-courses returns true. Actually, I was a little bit confused when I first saw the codes.
And necessary for time complexity to be O(num_nodes). If we didn't do it, the last for loop would have us visiting nodes as many times as it required by other courses, making the overall complexity O(n^2).
Your channel is soo helpful! If I get stuck on a LC question I always search for your channel! Helped me pass OAs for several companies. Thank you so much.
If you move the line 13 `if preMap[crs] == []` before the line 11 `if` check, then you don't need the `visitedSet.remove(crs)` in line 19, because you will never traverse the visited path that way. Thanks for great explanation.
this is a clever solution. not something i would ever come up with haha, i had a similar idea, but it kind of just broke down during the dfs step. i had a lot of trouble trying to figure out how to detect cycles in a directed graph...in the end when i was looking in the discussion i saw that you could just do a topological sort so i felt silly after that haha. gotta work on graph problems more :-)
I was really confused about the direction of the edges. Intuitively, I would think precourse -> course, but you have the arrows going backwards from course -> precourse. By switching the arrows around to: precourse -> course, and having your adjacency list as: { precourse: [ course ] } instead of: { course: [ precourse ] }, your DFS solution still works. The benefit to doing it this way is that you can use the same adjacency list pattern for a BFS topological sort approach, which needs access to the neighbors of nodes with zero in-degrees.
To simplify this problem This is based on finding if the directed graph has a cycle. If yes then return false(cannot complete all courses) else return true.
Here is a simpler solution. Instead of removing and adding from a map, we simply use a status 0 -> unvisited, 1-> visiting, and 2->visited for tracking the current node status in a DFS path. If the node is revisited before completing all neighbors, it would have status 1 which implies there is a cycle in the graph. Same logic as Neetcode's though. class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = [[] for _ in range(numCourses)] visit = [0]*numCourses for u,v in prerequisites: graph[u].append(v) def dfs(node): if visit[node] == 1: return False if visit[node] == 2: return True visit[node] = 1 for neighbor in graph[node]: if not dfs(neighbor): return False visit[node] = 2 return True for i in range(numCourses): if visit[i] == 0: if not dfs(i): return False return True
Great explanation, I was doing the adj list pre->course and confused myself in the coding step. Thanks for the video, smart ideas. I definitely was not thinking of the fully connected graph case
Thank you so much for all of these videos. Very well explained and also well put together and displayed. Really fantastic material, it's been absolutely invaluable in helping me to learn and improve my skills.
You draw edge incorrectly. If it's [0, 1] meaning you first have to take course 1 before 0, edge is gonna be 1->0, not 0->1, because first we need to take 1 and only then we will have access to the 0.
I have taken Neetcode's Course Schedule 2 idea and implemented this on those lines: Personally I found that idea more intuitive and easier to follow. 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
Java version of this solution: class Solution { Map preMap = new HashMap(); Set visitSet = new HashSet(); public boolean canFinish(int numCourses, int[][] prerequisites) { for (int i = 0; i < numCourses; i++) { preMap.put(i, new ArrayList()); } for (int[] p : prerequisites) { List neighbors = preMap.get(p[0]); neighbors.add(p[1]); preMap.put(p[0], neighbors); } for (int i = 0; i < numCourses; i++) { if (!dfs(i, preMap, visitSet)) return false; } return true; } public boolean dfs(int course, Map preMap, Set visitSet) { if (visitSet.contains(course)) return false; if (preMap.get(course).size() == 0) return true; visitSet.add(course); for (int pre : preMap.get(course)) { if (!dfs(pre, preMap, visitSet)) return false; } visitSet.remove(course); preMap.put(course, new ArrayList()); return true; } }
Thanks for the very clear explanation. I have a suggestion for direction of arrows that may be less confusing. For example, prerequisites = [[1,0]] means that if we have to take course 0 before course 1. So my graph would be pictured like: 0------->1 instead of 1------>0.
in the example case [1,0], why is it out reach arrow 1-> 0 ? I thought in order to get 1, you need to get 0 first, so, it's 0->1 ? am i right? it's a little anti-intuitive ?
I have a hard time envisioning visited.remove(crs). I cannot connect this to the "Drawing Solution" earlier. I can see when preMap[crs] is set to 0 @7:44, but I cannot see any part where visisted.remove(crs) corresponds to. I understand to detect a cycle, we need to visisted.add(crs), But I cannot see where visited.remove(crs) fits. Can someone help?
Lets say course 3 is dependent on 2 and 2 is on 1, while traversing for 3 you make dfs(2) which in turn is dfs(1) but dfs(1) does not have pre-req so u mark it as [] (initially) and similarly you need to mark dfs(2) to [] which is done using set.remove() and map.append([] ) for key =2 .
Same. What helped me was thinking about it as setting the course node to a "leaf node". If you notice the leaf nodes (courses with no prerequisites) are never added to the visited set. So setting it to [] and removing it from the set does that.
I think it makes more sense if you replace visitSet.remove() with visitSet.clear(). visitSet.clear() also works for our purpose, which is basically to give us a new visitSet for each course so we don't get false positives from earlier runs.
When the graph is not fully connected. 1->2->3, 4->3. If you should not remove 3, 4->3 would be false because 3 is already in the set. However, you can also choose to change the order of the two ifs in the start of the bfs to avoid removing.
I implemented DFS via a stack. I also tried a similar approach with BFS using a deque queue but it was a lot slower. class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) for prereq in prerequisites: graph[prereq[0]].append(prereq[1]) for i in range(numCourses): if i in graph: stack = graph[i] seen = set() while stack: node = stack.pop() if node == i: return False if node not in seen: for j in graph[node]: stack.append(j) seen.add(node) return True
Hey man, thanks a lot for your description. You probably have the best explanation on this this problem compared to other RUclipsrs. There’s a girl that’s pretty good too her names jenny
Given N = number of courses, P = prerequisites; TC: O(N + P), because we are visiting each "node" once, and each "edge" once as well. SC: O(N+P), as our hashmap is of size N + P, and the recursive call stack + visited set are of size N.
Intuitively I was thinking of this solution and gave myself 30 mins to solve it, I got to the part of DFS but then confused myself because I was like "I feel like I need DFS here but where should I start it, how should I call it" and then the time was up xD, I'm happy I almost came up with it alone though. Thanks for the video, it clarified what I was having trouble with.
Thanks for your explanation! it is clean and easy to percept. I really appreciate your coding style. Just a heads up that the if perMap[crs] == [] return True can be omitted since if we have an empty array for prerequisites for crs, the for loop afterwards will just end and return True at the end!
When talking about graphs in your Data Structures and Algorithms course, I think this may have been a missed opportunity to cover some pragmatic cycle detection algorithms - for DAG and for undirected graphs. I'm not telling you anything you don't already know, but this just cycle detection in a DAG that is not necessarily a connected graph. Those concepts are more broadly applicable to the next Course Schedule problem, which uses Topological Sort, and Topological sort follows DAG cycle detection well.
When I did this exercise for the first time, I actually created a whole complete graph data structure from scratch. Then created 2 visited maps to resolve the circular issue. So much memory required
When we loop over numCourses and do a dfs on each node, are we not doing repeated work? For instance starting with node 0 and going over the entire graph, we know that dfs(1) would be true, dfs(2) would be true etc. So we're unnecessarily repeating the dfs right? And so the TC would also be V*(V+E) ?
I feel using Kahn's algorithm for detecting cycles in the directed graph is the simplest solution for this, even though logically not 100% right as we use indegree in Kahn's algorithm, as soon as I see cycle and undirected graph I solved it with this method. Then I got to know we are supposed to deal with outdegree to deal with independent nodes in this case! Though Kahn's algo works !
This is very clear explanation, but I met Time Limit Exceeded problem, so I made the follow changes to met the requirements: class Solution(object): def canFinish(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """ adjacency_list = [[] for _ in range(numCourses)] for crs, prec in prerequisites: adjacency_list[crs].append(prec)
visited = [0] * numCourses def dfs(crs): if visited[crs] == 1: return False if visited[crs] == 2: return True visited[crs] = 1 for prec in adjacency_list[crs]: if not dfs(prec): return False visited[crs] = 2 return True for crs in range(numCourses): if not dfs(crs): return False return True
@NeetCode Thank you so much for your work! I'am going through collection of your solutions and litterally feeling smarter) I don't really understand one thing in this problem - why do they provide numCourses at all? I mean, when given number is less then total number of courses provided in prerequisites - like (1, [[0, 1]]) the algorithm fails. And of course you dont realy need this number to create preMap (you could use defaultdict, or check if key exists on string 14 before comparing to empty list). Iteration through length of preMap also will work when running dfs.
Explanation on WHY/HOW cycle was detected(The crux of the problem) -As we perform dfs, we add node to 'visited' set if it does not exist. -Once we have exhausted all its neighbors/prerequisites AND return back to it from call stack, we pop it from call stack and we remove from 'visited' set. -A cycle is detected when the node we are popping off of call stack still exists in 'visited' set. BUT WHY?? In the last example he provides @ 10:50, while we have/are visiting the last neighbor/prepreq of node 0, unfortunately we have not returned back to it due to its order in call stack. Hence a cycle was detected before we we're able to remove node 0 from call stack.
I have to say if you didn't realize this was a graph problem or to just think about it literally initially about courses and prerequisites you can get pretty stuck with where to go. :(
we dont need to travese 4 from 1 if we are keeping track of the visited nodes. cross edge iterations can be eliminated to increase the speed of the algorithm, right?
how come you don't use a set instead of a list for the visitedSet? One would need to use the nonlocal keyword but the lookup times are much quicker. Couldn't there be an edge case where your last node in the dfs loops back to the second to last and then you are searching the whole array. This could potentially happen a couple times no? Thanks for any clarity you can provide!
The way you set up the edges is very unintuitive. I think of it as if 0 is a prerequisite for 1 then 0 -> 1. So you'd traverse the graph in the order you would take the classes. Otherwise good video!
Quick question: I was trying to solve this using the Ailen Dictionary method you also made a video of. I can't get it to pass all test cases. May I ask if the method for the alien dictionary can be applied to this one?
I understand the preMap[crs] == [] purpose. But, does that mean when we find out that a course's prerequisite is [], we directly conclude that this course can be completed and return true for that course, without checking if the other prerequisites of that same course can all be completed as well? In other words, do we consider that a course can be completed if at least one of its prerequisites can be so?
Why can't your map be an integer as the key and an integer as the value? Why does the value have to be a list? I thought it would be okay to declare the map as int, int since you have one prereq for each course
Simpler version (imo): class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: pre = collections.defaultdict(list) for e in prerequisites: pre[e[0]].append(e[1]) visited = set() completed = set() def dfs(node): if node in visited and node not in completed: return False if node in visited: return True visited.add(node) res = all(dfs(child) for child in pre[node]) completed.add(node) return res return all(dfs(n) for n in range(numCourses))
Could another solution be just detecting if the graph contains a cycle or not? You would use 2 pointers and make one move by one position and the other by 2. If the nodes encounter each other then you will have a cycle therefore you can’t complete the courses. Could someone tell me if there is a flaw in this solution? Thanks :)
I don’t really get what If not dfs(pre): Return false Is doing. I understand it’s checking if the statement is false but what is it doing specifically?
Is it just me or does it seem like Leetcode has added a testcase for this problem that causes it to exceed time limit, even with this great implementation? Cannot get a pass for this problem...
Your videos are excellent in deriving solutions for any given problem ! However some of the cool things you do in python are not available exactly in other lang,(java).I'm writing java code using " drawing solution" explanation section from your videos, sometimes I find it easy, sometimes I struggle to write in equivalent lang using your approach (although 100 of solutions are out there ready-made using diff approaches ). I know its too much to ask it would be really cool if links for other languages are added in description (cpp/java):D But either-wise ,keep doing these videos irrespective of languages as "concepts is the core " ! Big shout out to you for one more super-awesome video :)
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
think of a directed graph 0->1->2->3->4, isn't your solution's time complexity O(E * N**2)...you will start the same loop for 1, 2, 3, 4 after doing it for 0
@@jchakrab No. Both the visitSet and updating preMap[course] to empty will ensure that we no longer need to start the same loop when processing nodes that's already visited.
The .remove(crs) was so confusing but I finally understood it. Simplest explanation: if we exit the for-loop inside dfs, we know that crs is a good node without cycles. However, if it remained in the visited set, we could trip the first if-clause in the dfs function if we revisit it and return False. That's what we don't want to do, because we just calculated that crs has no cycles. So we remove it from visited so that other paths can successfully revisit it.
Basically we can visit the node twice without it being a cycle due to it terminating multiple paths.
and the reason it terminates at 'twice' is because of preMap[crs] = []
thank you! i was pulling out my hair trying to figure out why
Actually you can see this trick in many graph, binary tree or other problems using back tracking. Because the visit set is only used to contain the current visit path. So whenever you exit the sub-function you create on this level, you have to pop the info you passed in before.
in every dfs, pop() or remove() after a call, is a standard process. you will see.
Do you have any example?
The setting of preMap[crs]=[] before return true is so smart!!! Absolutely love it
Pretty smart! He removes all pre-courses at once after iterate through one adjacency list. In the drawing solution, he removes the pre-courses one by one. To align with the codes, the list can only be "cleaned out" if all pre-courses returns true. Actually, I was a little bit confused when I first saw the codes.
@@yuemingpang3161 what is the time and space complexity of this solution??
And necessary for time complexity to be O(num_nodes). If we didn't do it, the last for loop would have us visiting nodes as many times as it required by other courses, making the overall complexity O(n^2).
It's too smart
not only smart, but essential for a good running time.. hell I fell there!!!
Your channel is soo helpful! If I get stuck on a LC question I always search for your channel! Helped me pass OAs for several companies. Thank you so much.
He is speaking the language of god.🔥🔥
If you move the line 13 `if preMap[crs] == []` before the line 11 `if` check, then you don't need the `visitedSet.remove(crs)` in line 19, because you will never traverse the visited path that way. Thanks for great explanation.
You can actually just remove it all together and it still passes lol
this is a clever solution. not something i would ever come up with haha, i had a similar idea, but it kind of just broke down during the dfs step. i had a lot of trouble trying to figure out how to detect cycles in a directed graph...in the end when i was looking in the discussion i saw that you could just do a topological sort so i felt silly after that haha. gotta work on graph problems more :-)
what is the time and space complexity of this solution??
@@alfahimbin7161 O(n + p) where n is the number of courses and p the prerequisites. The explain it at around 08:37
Thank you so much pal! I was able to crack it myself after seeing your visualizations of the graph, with ease. Words can't describe my happiness.
what is the time and space complexity of this solution??
I was really confused about the direction of the edges. Intuitively, I would think precourse -> course, but you have the arrows going backwards from course -> precourse. By switching the arrows around to: precourse -> course, and having your adjacency list as: { precourse: [ course ] } instead of: { course: [ precourse ] }, your DFS solution still works. The benefit to doing it this way is that you can use the same adjacency list pattern for a BFS topological sort approach, which needs access to the neighbors of nodes with zero in-degrees.
this was so so helpful, thank you so much for being so clear!
Glad it's helpful!
To simplify this problem
This is based on finding if the directed graph has a cycle. If yes then return false(cannot complete all courses) else return true.
I feel the way the problem is worded, I never realized that it was asking this question lol
I find using topological sort for this task much more intuative and easier to implement
What a lucid explanation! Keep this up!
what is the time and space complexity of this solution??
Here is a simpler solution. Instead of removing and adding from a map, we simply use a status 0 -> unvisited, 1-> visiting, and 2->visited for tracking the current node status in a DFS path. If the node is revisited before completing all neighbors, it would have status 1 which implies there is a cycle in the graph.
Same logic as Neetcode's though.
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
visit = [0]*numCourses
for u,v in prerequisites:
graph[u].append(v)
def dfs(node):
if visit[node] == 1:
return False
if visit[node] == 2:
return True
visit[node] = 1
for neighbor in graph[node]:
if not dfs(neighbor):
return False
visit[node] = 2
return True
for i in range(numCourses):
if visit[i] == 0:
if not dfs(i):
return False
return True
Great explanation, I was doing the adj list pre->course and confused myself in the coding step. Thanks for the video, smart ideas. I definitely was not thinking of the fully connected graph case
Thank you so much for all of these videos. Very well explained and also well put together and displayed. Really fantastic material, it's been absolutely invaluable in helping me to learn and improve my skills.
LintCode imposes the memory constraint such that recursive DFS will fail.
The intended solution should be iterative based topological sort.
If you want to take course 1, you have to take course 0 first.
You draw edge incorrectly. If it's [0, 1] meaning you first have to take course 1 before 0, edge is gonna be 1->0, not 0->1, because first we need to take 1 and only then we will have access to the 0.
his solution models the graph in the other direction, it is still correct because he is consistent with it
I was thinking the same thing, the arrows threw me off
The arrows/wording is messed up, he’s using the word prerequisite to actually mean postrequisite, but good video still
yeah all his arrows are backwards I don't know how that makes sense to him.
I have taken Neetcode's Course Schedule 2 idea and implemented this on those lines:
Personally I found that idea more intuitive and easier to follow.
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
I literally looked at this question yesterday and couldn’t get it, thanks for making this vid!
A nice coincidence! Thanks for watching
Java version of this solution:
class Solution {
Map preMap = new HashMap();
Set visitSet = new HashSet();
public boolean canFinish(int numCourses, int[][] prerequisites) {
for (int i = 0; i < numCourses; i++) {
preMap.put(i, new ArrayList());
}
for (int[] p : prerequisites) {
List neighbors = preMap.get(p[0]);
neighbors.add(p[1]);
preMap.put(p[0], neighbors);
}
for (int i = 0; i < numCourses; i++) {
if (!dfs(i, preMap, visitSet)) return false;
}
return true;
}
public boolean dfs(int course, Map preMap, Set visitSet) {
if (visitSet.contains(course)) return false;
if (preMap.get(course).size() == 0) return true;
visitSet.add(course);
for (int pre : preMap.get(course)) {
if (!dfs(pre, preMap, visitSet)) return false;
}
visitSet.remove(course);
preMap.put(course, new ArrayList());
return true;
}
}
you saved me! Thankssss!
@@tamilcodingclub3832 Instead of preMap.put(course, new ArrayList()); you can do preMap.get(course).clear(); It saves memory
you are the very best one for explain leetcode problems, and I am not even a python user
Thanks! =)
Thanks for the very clear explanation. I have a suggestion for direction of arrows that may be less confusing. For example, prerequisites = [[1,0]] means that if we have to take course 0 before course 1. So my graph would be pictured like: 0------->1 instead of 1------>0.
Depends on how we see it. In his case, the concept is like 1 has a dependency on 0, hence drew an edge from 1 pointing towards 0.
Yeah that was so confusing
in the example case [1,0], why is it out reach arrow 1-> 0 ? I thought in order to get 1, you need to get 0 first, so, it's 0->1 ? am i right? it's a little anti-intuitive ?
I have a hard time envisioning visited.remove(crs). I cannot connect this to the "Drawing Solution" earlier. I can see when preMap[crs] is set to 0 @7:44, but I cannot see any part where visisted.remove(crs) corresponds to.
I understand to detect a cycle, we need to visisted.add(crs), But I cannot see where visited.remove(crs) fits.
Can someone help?
Lets say course 3 is dependent on 2 and 2 is on 1, while traversing for 3 you make dfs(2) which in turn is dfs(1) but dfs(1) does not have pre-req so u mark it as [] (initially) and similarly you need to mark dfs(2) to [] which is done using set.remove() and map.append([] ) for key =2 .
Same. What helped me was thinking about it as setting the course node to a "leaf node". If you notice the leaf nodes (courses with no prerequisites) are never added to the visited set. So setting it to [] and removing it from the set does that.
I think it makes more sense if you replace visitSet.remove() with visitSet.clear(). visitSet.clear() also works for our purpose, which is basically to give us a new visitSet for each course so we don't get false positives from earlier runs.
When the graph is not fully connected. 1->2->3, 4->3. If you should not remove 3, 4->3 would be false because 3 is already in the set. However, you can also choose to change the order of the two ifs in the start of the bfs to avoid removing.
feel the same thing.
without the empty list optimization this will get TLE, pretty smart to figure that out
you dont need to remove crs from visited at the end if you just check adj==[crs] before checking crs in visitSet
huh ?
Thank you! Great explanation! And you have a magical voice, such a pleasure to listen to your explanations.
I implemented DFS via a stack. I also tried a similar approach with BFS using a deque queue but it was a lot slower.
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
for prereq in prerequisites:
graph[prereq[0]].append(prereq[1])
for i in range(numCourses):
if i in graph:
stack = graph[i]
seen = set()
while stack:
node = stack.pop()
if node == i:
return False
if node not in seen:
for j in graph[node]:
stack.append(j)
seen.add(node)
return True
Though it doesn't matter, but in line 5 and 6 , premap[pre].append(crs) - the way the input is given
Hey man, thanks a lot for your description. You probably have the best explanation on this this problem compared to other RUclipsrs. There’s a girl that’s pretty good too her names jenny
clear solution, thank you! Wish you could also go over BFS 😄
Brilliant Solution!! It took me a while to think it through but finally understood it, really appreciate your help!
Could you also go through the space complexity in your videos?
Given N = number of courses, P = prerequisites; TC: O(N + P), because we are visiting each "node" once, and each "edge" once as well. SC: O(N+P), as our hashmap is of size N + P, and the recursive call stack + visited set are of size N.
Intuitively I was thinking of this solution and gave myself 30 mins to solve it, I got to the part of DFS but then confused myself because I was like "I feel like I need DFS here but where should I start it, how should I call it" and then the time was up xD, I'm happy I almost came up with it alone though. Thanks for the video, it clarified what I was having trouble with.
Thanks for your explanation! it is clean and easy to percept. I really appreciate your coding style.
Just a heads up that the if perMap[crs] == [] return True can be omitted since if we have an empty array for prerequisites for crs, the for loop afterwards will just end and return True at the end!
Yes, though, you save "some time" by handling it that way.
When talking about graphs in your Data Structures and Algorithms course, I think this may have been a missed opportunity to cover some pragmatic cycle detection algorithms - for DAG and for undirected graphs.
I'm not telling you anything you don't already know, but this just cycle detection in a DAG that is not necessarily a connected graph. Those concepts are more broadly applicable to the next Course Schedule problem, which uses Topological Sort, and Topological sort follows DAG cycle detection well.
When I did this exercise for the first time, I actually created a whole complete graph data structure from scratch.
Then created 2 visited maps to resolve the circular issue. So much memory required
You explanaition is amazing, I love it !
Glad it's helpful!
When we loop over numCourses and do a dfs on each node, are we not doing repeated work? For instance starting with node 0 and going over the entire graph, we know that dfs(1) would be true, dfs(2) would be true etc. So we're unnecessarily repeating the dfs right? And so the TC would also be V*(V+E) ?
I feel using Kahn's algorithm for detecting cycles in the directed graph is the simplest solution for this, even though logically not 100% right as we use indegree in Kahn's algorithm, as soon as I see cycle and undirected graph I solved it with this method.
Then I got to know we are supposed to deal with outdegree to deal with independent nodes in this case!
Though Kahn's algo works !
Your explanation is super clear, thanks
what is the time and space complexity of this solution??
This is very clear explanation, but I met Time Limit Exceeded problem, so I made the follow changes to met the requirements:
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
adjacency_list = [[] for _ in range(numCourses)]
for crs, prec in prerequisites:
adjacency_list[crs].append(prec)
visited = [0] * numCourses
def dfs(crs):
if visited[crs] == 1:
return False
if visited[crs] == 2:
return True
visited[crs] = 1
for prec in adjacency_list[crs]:
if not dfs(prec):
return False
visited[crs] = 2
return True
for crs in range(numCourses):
if not dfs(crs):
return False
return True
@NeetCode Thank you so much for your work! I'am going through collection of your solutions and litterally feeling smarter)
I don't really understand one thing in this problem - why do they provide numCourses at all? I mean, when given number is less then total number of courses provided in prerequisites - like (1, [[0, 1]]) the algorithm fails. And of course you dont realy need this number to create preMap (you could use defaultdict, or check if key exists on string 14 before comparing to empty list). Iteration through length of preMap also will work when running dfs.
+1
this question is currently being asked at Amazon. My brother is one of the interviewers who asks it hehe
Nice explanation. Curious - why/how did you zero in on using DFS instead of BFS?
@rahul, to check if a particular course completion can be possible. And we can do it if and only if we can check all its prerequisite.
I don’t quite understand. Is it about topological sort or some other kind of algorythm? Like finding cycles for example
Explanation on WHY/HOW cycle was detected(The crux of the problem)
-As we perform dfs, we add node to 'visited' set if it does not exist.
-Once we have exhausted all its neighbors/prerequisites AND return back to it from call stack, we pop it from call stack
and we remove from 'visited' set.
-A cycle is detected when the node we are popping off of call stack still exists in 'visited' set.
BUT WHY??
In the last example he provides @ 10:50, while we have/are visiting the last neighbor/prepreq of node 0, unfortunately we have
not returned back to it due to its order in call stack. Hence a cycle was detected before we we're able to remove node 0 from call stack.
thanks for the n = 5 expample, cleared the ques for me !
Forgot the remove part. You are amazing
I meet this question today, thank you so much.
Thanks Neetcode!
Is this playlist supposed to be followed sequentially?
Thanks
I have to say if you didn't realize this was a graph problem or to just think about it literally initially about courses and prerequisites you can get pretty stuck with where to go. :(
we dont need to travese 4 from 1 if we are keeping track of the visited nodes. cross edge iterations can be eliminated to increase the speed of the algorithm, right?
Phenomenal explanation! Thank you so much!
Thank you for this awesome video! I am wondering if you could do a video about a BFS version of the same problem? Thank you very much!
SO clear! Thanks a lot
Killer explanation. Thank you.
how come you don't use a set instead of a list for the visitedSet? One would need to use the nonlocal keyword but the lookup times are much quicker. Couldn't there be an edge case where your last node in the dfs loops back to the second to last and then you are searching the whole array. This could potentially happen a couple times no? Thanks for any clarity you can provide!
in the question, is numCourses representing the number of course you can take or the list of courses you have to take?
you can use a defaultdict(list) instead for preMap :)
Bro, you are just GOLD!
I think you have it backwards around 1:19 but no big deal. 1 is a prereq of 0
The way you set up the edges is very unintuitive. I think of it as if 0 is a prerequisite for 1 then 0 -> 1. So you'd traverse the graph in the order you would take the classes. Otherwise good video!
good explanation on dfs, thanks! and i like the name of your channel :)
Happy it's helpful :)
so isnt it just a detect cycle problem? if cycle exists return false else true ?
Love your videos! Would love to see the code included as well, especially in Javascript as converting can be tough. Thanks NeetCode :)
I tackled this problem as cycle detection.
Quick question: I was trying to solve this using the Ailen Dictionary method you also made a video of. I can't get it to pass all test cases. May I ask if the method for the alien dictionary can be applied to this one?
So amazing brother. Thank you
In the beginning you show the edge going the wrong way for [1,0] the direction of the arrow should be from 0 to 1
Very nice. Thanks for making this
Lines 13 and 14 are redundant. if preMap[crs] == [], code will skip the for loop and return True at L 21 already
In case others come across this, these types of questions are classified under Topological Sort as well
He's using a hacky method instead of topological sort.
Any resources on Topological Sort?
Or, do you have any leetcode problems and solutions that you've implemented using topo sort?
What is the space complexity ? Since we are using HashMap and Set?
I understand the preMap[crs] == [] purpose. But, does that mean when we find out that a course's prerequisite is [], we directly conclude that this course can be completed and return true for that course, without checking if the other prerequisites of that same course can all be completed as well? In other words, do we consider that a course can be completed if at least one of its prerequisites can be so?
preMap[crs] == [] is outside of the loop so by then we ensured all prerequisites can be completed
Great video. I wonder if you could solve this problem with a tortoise & hare algorithm?
I came up with the same idea but didn't know how to code. How should I improve?
Is this considered topological sort?
Why can't your map be an integer as the key and an integer as the value? Why does the value have to be a list? I thought it would be okay to declare the map as int, int since you have one prereq for each course
Thank you!!! Such a great teacher
Simpler version (imo):
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
pre = collections.defaultdict(list)
for e in prerequisites:
pre[e[0]].append(e[1])
visited = set()
completed = set()
def dfs(node):
if node in visited and node not in completed:
return False
if node in visited:
return True
visited.add(node)
res = all(dfs(child) for child in pre[node])
completed.add(node)
return res
return all(dfs(n) for n in range(numCourses))
Could another solution be just detecting if the graph contains a cycle or not? You would use 2 pointers and make one move by one position and the other by 2. If the nodes encounter each other then you will have a cycle therefore you can’t complete the courses. Could someone tell me if there is a flaw in this solution? Thanks :)
You wouldn't detect isolated courses
I don’t really get what
If not dfs(pre):
Return false
Is doing. I understand it’s checking if the statement is false but what is it doing specifically?
Thank you so much!
You are legend man!!!
why do we have to remove the crs from the visited set at line 19? what is the purpose?
Brilliant explanation, wow.
Hello everyone, this is YOUR daily dose of leetcode solutions
Is it just me or does it seem like Leetcode has added a testcase for this problem that causes it to exceed time limit, even with this great implementation? Cannot get a pass for this problem...
Did you set the dependencies list to empty after a node is searched? This would save a lot of time
Your videos are excellent in deriving solutions for any given problem ! However some of the cool things you do in python are not available exactly in other lang,(java).I'm writing java code using " drawing solution" explanation section from your videos, sometimes I find it easy, sometimes I struggle to write in equivalent lang using your approach (although 100 of solutions are out there ready-made using diff approaches ). I know its too much to ask it would be really cool if links for other languages are added in description (cpp/java):D But either-wise ,keep doing these videos irrespective of languages as "concepts is the core " ! Big shout out to you for one more super-awesome video :)
btw how did u got official account
If you understand the logic, it doesn't matter what language it's done in. Logic is language agnostic. The only difference is syntax. Good luck!
Awesome solution!
@NeetCode Can you please explain the time complexity in detail.
I think my algorithm was right, but it ended up timing out on the last test case which made me sad
Thank you neetcode guy
Thanks for this wonderful video!
Thanks!
this is actually a cycle detection problem. I have no idea why the problem was framed as an adjacency graph problem
looking sharp thanks
Wow... The best explaination... ❤️