207. Course Schedule

Leetcode #: 207
Name: Course Schedule
Difficulty: Medium
Url: https://leetcode.com/problems/course-schedule/

Prompt

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.- For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.Return true if you can finish all courses. Otherwise, return false.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Approach

Prompt Diagnosis

The prerequisites are given as a list where each element within the list are subarrays. The problem statement indicates that you must take the 2nd element within the subarray or course first if you want to take the 1st element within the subarray or course.

This is important to note because this is essentially how we should be thinking of our graph where every node or course has a directed edge or pointer to its prerequisite course(s).

Implementation

As we’re given a list of prerequisites, we should first form our adjacency list to represent our graph. We can create an adjacency list using a Hash Map and setup the keys of the Hash Map as each of the courses that we can possibly take. In this case, it’s convenient because we can simply iterate through the given numCourses which are labeled from 0 to numCourses — 1 so in other words, the numCourses given represents all of the courses we can possibly take.

We’ll want to populate our Hash Map or adjacency list after creating the key:value pairs of the keys consisting of the courses and values consisting of empty lists at first with each of the courses’ respective prerequisite courses.

Once we have our adjacency list populated with each course along with their prerequisite course(s), we should perform our traversing algorithm (DFS or BFS). I’ll go ahead and execute a brute-force DFS backtracking algorithm.

In our DFS algorithm, we’ll want to first setup our base cases as the inherent nature of a DFS algorithm is recursive. We’ll want to instantiate a Hash Set so we could keep track of the nodes that we’ve explored or iterated as we traverse through our graph.

The first base case will be checking if the starting course is already in our Hash Set. If it is, we want to return False because at that point, we know that we’ve looped around the graph and have encountered a cycle. If we encounter a cycle, we know that it’s impossible to finish all the courses as every course has a prerequisite requiring another. If that’s true for all courses, then there isn’t a course in which we can start.

The second base case we’ll be checking for is if length of the list that contains the prerequisites of the course that I’m currently examining is empty, then we know we can return True because we know then that the course that we are currently examining that has met this base case isn’t a course that requires a prerequisite.

If we haven’t met either 2 of these base cases, we’ll want to add the course that we are currently iterating into our Hash Set. Subsequently, we’ll examine any prerequisite course(s) of the course that we are currently iterating if there are any by invoking a recursive DFS call on those prerequisite course(s) or neighbors. If any of those recursive DFS call(s) return False, then we know that we can return False because we have found a cycle in a prerequisite course.

If we make it out of the examination of each prerequisite course or neighbor, then we know at that point that we have a valid path which indicates that you can finish all courses so we can return True. But before we return True, we’ll want to remove the course that we are currently iterating from our Hash Set to all other nodes to iterate through this same node if necessary (i.e. backtracking). We’ll also want to replace the list of prerequisites or value of the key:value pair of the course that we are currently iterating to an empty list so that if any other node happens to have this same node that we are currently iterating as one of its prerequisite courses, then we can not perform the main body of the DFS algorithm and instead return from the 2nd base case I mentioned earlier where we check if the length of the prerequisite course(s) list is empty, which in this case should be and therefore return True.

Finally, in the outer call on our DFS algorithm, we’ll want to loop through each possible course from the given numCourses and call our DFS algorithm on each course. This is because we might have a scenario in which the graph isn’t entirely connected meaning that we can have nodes in their own separate islands. Therefore, we’re solving that edge case by iterating through every single course possible to check to see if we can finish all courses. If we don’t return False from any of these DFS calls on any of these courses which again signifies that we’ve detected a cycle, then we can confidently return True from our outer function.

Code

Python | Time: O(n + P) where n is the # of nodes or vertices and P is the # of prerequisites or edges | Space: O(n) where n is the # of nodes or vertices

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com