Course Schedule (LeetCode #209)

Image by Kenny Eliason on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Implement Trie.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Course Schedule problem, you’re in the right spot.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

Let’s get it started!

Understanding the Problem 🕵🏻‍♂️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given a numCourses integer that represents the total courses available to take
2. We’ll be given a list of prerequisites of [a, b] where b is the course that needs to be taken before a
3. We should return True if all courses can be taken given the prerequisites or return False if they can’t
4. numCourses will be 1 <= numCourses <= 2000
5. The length of prerequisites will be 0 <= len(prerequisites) <= 5000
6. Each value within prerequisites will be a list of length 2 with two integers in it representing two courses

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Okay. I think that’s enough housekeeping items for us to get started!

Initial Setup 🏗

This is the second graph problem I’ve covered in my articles (the first being Clone Graph), but it’s the first one where we really get into some interesting traversal work.

We’re going to be doing a depth-first search traversal of our graph while caching outcomes along the way. This will enable us to only traverse each node’s prerequisites once and then reuse the results thereafter.

The first bit of setup we need to do is to map our courses to all prerequisites.

We can do that by first defining an int to list setup in a dictionary for every course from 0 up to (but not including) numCourses. This is because our courses in our prerequisites list are zero-indexed.

This is what that looks like:

This will produce a dictionary that looks something like this:

{ 0: [], 1: [], 2: [], ... on up to num_courses - 1 }

From here, we need to initialize an empty cache dictionary and also populate our courses_to_prereqs dictionary with data:

The for loop iterates through prerequisites and, for every pair of a [course, prereq], pushes the prereq to the list for that course in courses_to_prerequisites.

For instances, a list of prerequisites like this:

prerequisites = [[0, 1], [2, 1]]

will not have a courses_to_prerequisites dictionary that looks like:

courses_to_prerequisites = {
  0: [1],
  1: [],
  2: [1],
}

From here, the next step is to set up our depth-first search traversal function!

Let’s get to it! 🔥

Setting Up Our Function 🌀

The first thing we need to do is to initialize a new function. We’ll call ours dfs_traversal:

The first thing we need to write inside our function are two quick exit cases.

1. We need to exit if the course is already stored in cache (and return its value)
2. We need to exist if the length of the current course's course_to_prerequisites list is length 0 (and return True since the current course has no prerequisites and therefore is automatically possible to take)

This is what these exit cases look like:

Next, we’re going to pre-populate our course value in cache to be False in case we exist early in the loop we’re about to write (you’ll see why in a second):

This will also keep us safe if we get ourselves into a recursive situation (e.g. 0 has a prerequisite of 1 and 1 has a prerequisite of 0).

After this, we can write a new for loop that will, for every prerequisite for the course (using data we’ve built in courses_to_prereqs), call dfs_traversal:

Each time, we’ll call dfs_traversal which adds to the call stack and traverses down deeper into the graph of prerequisites.

When this call does return, we’ll instantly return False if that’s the value we received (as there’s no point in continually calling more of the other prerequisites — we know this course’s prerequisite can’t be taken).

Otherwise, we continue with our loop.

When it’s done, this means that we traversed all the prerequisites and none of them returned False.

We can now set the cache value for the course to True. After that, we can just return True:

All that’s left for us to do is to write a loop that, for every course in courses_to_prerequisites, calls dfs_traversal.

If we get a False returned value at any point, we know the entire course structure is wrong.

At the very end, we can honestly just return True. We’ve fulfilled all the requirements for the course schedule and nothing has returned False. We’re done!

This algorithm will run in O(V + E) time where V is the number of vertices (courses) and E is the number of edges (connections to prerequisites). We only need to visit each course once before it’s cached.

The space complexity is also O(V + E).

Conclusion

Great job. Graph problems can be tough, but you made it. 🙌🏻

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)