Course Schedule II - Topological Sort - Leetcode 210

0:00 - Read the problem
2:25 - Drawing explanation
10:40 - Coding explanation

leetcode 210

#graph #topological #python

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

[tenkara]

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

[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.

[expansivegymnast]

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

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

[parmanandabanakar]

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)

[raevenbauto]

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

[MrEdgoll]

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

[rahul]

For people who want to learn Course Schedule I on the lines of this concept discussed here:

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;
}
}

[servantofthelord]

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

[tanishbansal]

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.

[harishsn]

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.

[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

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

[harrydalal]

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

[yustdream]

very clean code with great explanation

[ronhu]

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

[niteshmanem]

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

[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

[bolinsun]

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