Course Schedule - Graph Adjacency List - Leetcode 207

0:00 - Read the problem
1:40 - Drawing Solution
10:50 - Coding solution

leetcode 207

#leetcode #graph #python

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[xmnemonic]

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.

[juliahuanlingtong]

The setting of preMap[crs]=[] before return true is so smart!!! Absolutely love it

[yynnooot]

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.

[saralee]

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.

[ax]

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?

[momentumbees]

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.

[idgafa]

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.

[yoshi]

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

[DarkOceanShark]

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.

[rahul]

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<Integer, List<Integer>> prereq = new HashMap<>();

// hashset to mark the visited elements in a path
HashSet<Integer> 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<Integer> currPath = new HashSet<>();

public boolean canFinish(int numCourses, int[][] prerequisites) {

// base case
if (numCourses <= 0)
return false;

// initially everything inside this prereq map is empty
for (int i = 0; i < numCourses; i++)
{
prereq.put(i, new ArrayList<Integer>());
}

// populate this prereq map now with the original values
for (int[] pre : prerequisites)
{

}

// call the function that is going to dfs through the graph
for (int i = 0; i < numCourses; i++)
{
if (dfs(i) == false)
return false;
}

// everything returned smoothly; return true
return true;

}

private boolean dfs(int i)
{
// lets check if our curr path already has seen this node
// we found a cycle so return false
if (currPath.contains(i))
{
return false;
}

// base case: check if this node has already been completed
// ie we have already studied this course
if (completed.contains(i))
{
return true;
}

// add this node to our current path
currPath.add(i);

// recurse and visit all its prerequisites
for (int pre : prereq.get(i))
{
boolean result = dfs(pre);

// if any one of these prereq courses cant be complete, we can return false as we cannot complete anything
if (result == false)
return false;
}

// remove this node from our current path as we might come across this node again
currPath.remove(i);

// we have completed this course so add it to our completed set
completed.add(i);

// we were able to complete this course so return true
return true;
}
}

[AustinCS]

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.

[tuandino]

I find using topological sort for this task much more intuative and easier to implement

[yumindev]

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 ?

[sanaa]

this was so so helpful, thank you so much for being so clear!

[xingdi]

If you want to take course 1, you have to take course 0 first.

[steffikeranranij]

What a lucid explanation! Keep this up!

[MinhNguyen-lzpg]

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

[samuelrobert]

Great explanation! But 9:48 Don't use array here as it requires O(n) for visited course lookup instead of O(1) when you use a set.

[baboonizm]

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.

[chloe]

Could you also go through the space complexity in your videos?