LeetCode 207 Course Schedule: DFS Cycle Detection, Step by Step

0:00I'm a senior AI engineer, and I've developed AI software factories that

0:05basically write all my code for me.

0:09Nevertheless, I still know how to code, and to prove it, I'm going to

0:13teach you how to approach a LeetCode problem.

0:17In this video, I'm going to talk about course schedule and how you can

0:21go about reading the problem and understanding the problem-solving skills to

0:28get the right answer.

0:29So if you want to get a tech job where you're making $200,000, $300,000,

0:34$400,000 per year, stop and save this video.

0:39Come back to it when you're ready to start studying LeetCode.

0:43Now, when you approach a problem like this, the first thing you want to

0:47know, the first thing that comes to top of your mind is this is

0:50a graph problem. And the reason why you know that instantly is because you

0:55use a spreadsheet like this that divides problems into different categories.

1:00So you have a category for dynamic programming.

1:03You have a category for graphs, a category for heaps, a category for arrays.

1:09You already know that this is a graph problem because you're using a spreadsheet

1:14like this or you've done enough practice problems to remember how to

1:20do it. So we know it's a graph problem.

1:23We're going to go here and we basically read the question and understand.

1:28It's basically asking us how to detect cycles in a graph.

1:34So to detect cycles in a graph, I'll first show you a graph.

1:39And with this picture, you can sort of see that with this example, there

1:45are no cycles. Let me type this out on the screen.

1:48So we have numCourses equals two, prerequisites equals one, zero.

1:54What this will look like if you draw the graph and we can see

1:58that we have no cycle.

2:00We have zero, which has no prerequisites.

2:05And we have one which has zero as a prerequisite.

2:09And we know this. How do we know this?

2:11How do we know how many courses we have?

2:13We are a total of numCourses.

2:16And so the high level approach to this problem is you're going to try

2:21to take every single course.

2:25If you take every single course and you have no cycle, there's no infinite

2:30recursion loop, then yes, you can finish the course load.

2:34But if while you're trying to take a course, you're in an infinite loop,

2:38you have a little cycle, then you're going to say, no, we can't finish

2:43the course. So this example here, pretty simple to see that we have no

2:47cycles. Course zero has no prerequisites.

2:51Course one only has course zero, which has no prerequisites.

2:54So we're going to return true.

2:57Now let's take a look at the second example here, where we have numCourses

3:02equals two and prerequisites equals this graph here.

3:06Let me draw it out on the screen right now.

3:09We have zero, and then prerequisite is one, and we have one, and the

3:13prerequisite is zero.

3:15And right off the bat, we see there's a cycle.

3:20We try to take course zero, but we first had to take course one.

3:23We try to take course one, we first had to take zero.

3:26This is a cycle.

3:28So we're going to return false.

3:32Now how do you write this up in code?

3:36Basically while you're on a current course, what you'll do is you're going to

3:41look at every single prerequisite.

3:44So let me actually draw this out right now.

3:49First let's just gather a list of all of our prerequisites.

3:53I'm going to erase all this on the screen, and I'm going to say

3:58for prereq and prerequisites, we're going to have a mapping,

4:05so it's called prereqMap.

4:08We're going to have a mapping of the course we're on to the prerequisites.

4:14And so basically the way we'll do this is we're going to say prereq

4:17zero. If prereq zero is in prereq

4:24map, then we're going to

4:30say prereqMap of prereq zero,

4:37dots

4:39append prereq zero or prereq one.

4:45We're basically going to append the actual prerequisite, and so otherwise if it's not

4:50already in the map, we're basically going to do the same thing, but we're

4:54going to say this is going to equal to the prerequisite.

5:01And then once we're done, we're just going to print the prereqMap, make sure we did it all

5:06correctly. You're allowed to run code during most interviews.

5:10If you can't run the code, you can at least draw it out, but

5:13you can run the code, make sure everything looks right.

5:16This looks right to me. This looks exactly like what I drew on the

5:20screen earlier. So the next thing I'm going to do is I'm going to

5:24remember several things.

5:27So number one, we're trying to detect cycles, and the strategy for detecting cycles

5:32is if we're visiting a node and we're visiting again, that is a cycle.

5:36So we're going to have a map of visiting or a set of things

5:40that we're visiting right now.

5:43And then we're also going to have another set that says can complete course.

5:49Basically we're going to save it in a little set that says we've already

5:52visited before. We determined that we can't complete it, so we don't have to

5:56go downstream and visit all these courses again.

5:58Like, there's basically a set of things that we know that we can complete.

6:04And so after we have that, what we're going to do, we know we're

6:06going to do depth-first search.

6:09So you can use breadth-first search as well, depth-first search is a little bit

6:12easier, it's just recursion.

6:14I'm going to type out the formula here, say pass, and we're going to

6:18implement that later.

6:20Right now what we're going to do is finish the rest of the function.

6:23So we're going to basically say for each course, for course and

6:29range of numCourses, we're going to basically say

6:35if I can't take the course, then I can't finish the course

6:41load, return false.

6:44But we can't return true here, but we basically have to first try to

6:49take every single course.

6:51We try to take every single course, and only after we've completed taking every

6:56single course can we return true.

7:00So we're not going to have any else statement, we're going to return true

7:03here. Again, let's just run the code, make sure things compile, and then we're

7:07going to get into the meat of the problem, getting this answer to be

7:12false. So let's implement our depth-first search.

7:16Number one, if course is in visiting, we return false.

7:22If course is in, you can complete the course,

7:29then we return true.

7:32And then at the very end, we want to return true, right?

7:38That's like the, we're going to turn on Boolean here, and let's actually implement

7:41the meat of the algorithm.

7:43Let's say we're going to get our prereqs, so prereqs equals

7:49prereqMap, and we could say prereqMap, of course, but what if the

7:54course is in the prereqMap?

7:56I don't remember if I implemented any logic here.

7:59I'm going to say prereqs equals prereqMap .get course, and

8:04then defaults to the empty array.

8:08And I'm going to say if length of prereqs equals zero, then I'm

8:14going to say we have no prereqs, so obviously we can return true.

8:18We have no prereqs for this course, so we can take the course.

8:21Obviously, we want to return true.

8:23And now we're going to, if we have prereqs, though, we need to see,

8:27can we take all of these prereqs, or do we get a cycle?

8:31So we need to remember to do several things here.

8:34So number one, we have to remember the visiting set.

8:37So let's say visiting set is a visiting.add the course.

8:41We do remember to remove it from the visiting set before we return.

8:46And finally, return true, again, we're basically creating a little cache here with can

8:51complete course, we want to add the course.

8:54If these steps are confusing, I can make a video going a little bit

8:58slower, but I'm trying to make it kind of fast.

9:02If we can complete the course, you know, we return true, then we then

9:06later on, we can kind of short circuit.

9:08That's sort of the idea behind this.

9:10So finally, we're going to iterate over all our prereqs.

9:12And prereqs, we're going to say if

9:18DFS, a prereq, if really if we can't take the course, same idea before,

9:25if we can't take the course, we return false.

9:29If we can take the course, we're not returning early, so we're not going

9:32to do anything here, we can't take the course, we return false.

9:36Otherwise, we don't do anything and this might be it.

9:40Let's run the code and see what happens.

9:45It looks like it runs for now.

9:47Let's click submit.

9:50LeetCode's UI changed a little bit and we're done.

9:54We got the right solution.

9:56Obviously, a real interview is going to talk to you about time complexity, they're

10:00going to ask you about space complexity.

10:02But this video is really describing how I break down the problem.

10:08If you have any questions at all, leave a comment below and I'll help you out.