Course Schedule
Medium
You are given numCourses and a list of prerequisites, where each element in prerequisites[i] = [a_i, b_i] means you must complete course b_i before taking course a_i. Write a function canFinish that returns True if it's possible to finish all courses, and False if it's not. You need to complete all the courses for the result to be True.
Assume there are no duplicate prerequisites, and numCourses is a non-negative number.
Examples
Input: numCourses = 3, prerequisites = [[2, 1], [1, 0]] Output: True Explanation: You can complete course 0 first, then course 1, and finally course 2. Input: numCourses = 4, prerequisites = [[3, 2], [2, 1], [1, 0], [0, 3]] Output: False Explanation: The prerequisites form a cycle, making it impossible to finish all courses. Input: numCourses = 5, prerequisites = [[4, 2], [3, 1], [2, 0]] Output: True Explanation: You can complete the courses in order from course 0 to course 4.
Our solution processes the input data to determine if it's possible to finish all courses given the prerequisite constraints. It constructs a directed graph where nodes represent courses and edges represent the prerequisite relationships. The solution employs a queue to manage nodes with zero in-degrees (courses with no remaining prerequisites) and uses a list to keep track of the number of prerequisites (in-degrees) for each course.
For each course with zero in-degrees, the solution dequeues it and processes its neighbors, reducing their in-degrees. If a neighbor's in-degree becomes zero, it is added to the queue. This approach ensures that all courses with no remaining prerequisites are processed and their dependencies are updated accordingly.
By maintaining a count of the number of processed courses, the solution can determine if all courses can be finished. If the count of processed courses matches the total number of courses, it implies that there are no cyclic dependencies, and thus all courses can be completed.
The solution uses a queue to efficiently manage courses with zero in-degrees and a vector to keep track of in-degrees. This method ensures that each course is processed only once, making the approach both clear and efficient.
Time Complexity: The solution has a time complexity of O(numCourses + numPrerequisites). This is because we process each course (vertex) and each prerequisite pair (edge) exactly once. The time complexity reflects the total number of courses (numCourses) and the number of prerequisite relationships (numPrerequisites).
Space Complexity: The solution uses O(numCourses + numPrerequisites) space for the adjacency list and the in-degree vector. The space complexity accounts for the storage needed for both the graph representation and the queue, which in the worst case, contains all courses.
Interview experiences
9 shared
Related questions
Course Schedules IIRelated courses
