207. Course Schedule#

Difficulty: Medium

Link to Problem: To see the Course Schedule problem on LeetCode, click here!

There are a total of numCourses courses 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.

Constraints:

  • 1 <= numCourses <= 2000

  • 0 <= prerequisites.length <= 5000

  • prerequisites[i].length == 2

  • 0 <= ai, bi < numCourses

  • All the pairs prerequisites[i] are unique.

Probelm Explanation:#

The problem is to determine whether it’s possible to complete a set of courses given a list of prerequisites. You are given the following:

  • numCourses: The total number of courses to be taken, labeled from 0 to numCourses - 1.

  • prerequisites: A list of prerequisite courses, where each element prerequisites[i] is a pair [ai, bi], indicating that you must take course bi before you can take course ai.

The goal is to check whether it’s possible to complete all the courses while respecting the prerequisite requirements. In other words, you need to determine if there are any circular dependencies in the course prerequisites that would prevent you from taking all the courses.

For example:

  • If numCourses is 2, and prerequisites is [[1, 0]], it means you have two courses, and you must finish course 0 before you can take course 1. In this case, it’s possible to complete all courses, so the function should return True.

  • If numCourses is 2, and prerequisites is [[1, 0], [0, 1]], it means you have two courses, but there’s a circular dependency where course 1 requires course 0 and course 0 requires course 1. In this case, it’s impossible to complete all courses, so the function should return False.

The problem is essentially about checking for the presence of cycles in a directed graph, where the courses are nodes, and the prerequisites represent directed edges between them. If there are no cycles, it’s possible to complete all courses; otherwise, it’s not possible.

Solution:#

Here’s a Python function to implement this algorithm:

from collections import defaultdict, deque
from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Create a graph using an adjacency list to represent the courses and their prerequisites.
        graph = defaultdict(list)  # Initialize an empty adjacency list.
        in_degree = [0] * numCourses  # Initialize an array to store in-degrees of courses.

        # Populate the graph and calculate in-degrees.
        for course, prerequisite in prerequisites:
            graph[prerequisite].append(course)  # Add the course as a neighbor to its prerequisite.
            in_degree[course] += 1  # Increment the in-degree of the course.

        # Initialize a queue with courses that have no prerequisites.
        queue = deque()
        for course in range(numCourses):
            if in_degree[course] == 0:
                queue.append(course)

        # Perform topological sorting.
        while queue:
            course = queue.popleft()  # Take a course with no prerequisites.
            numCourses -= 1  # Decrement the count of remaining courses.

            for neighbor in graph[course]:
                in_degree[neighbor] -= 1  # Remove the prerequisite relationship.
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)  # If no more prerequisites, add to the queue.

        # If all courses were successfully taken (numCourses becomes 0), return True.
        return numCourses == 0

Explanation:#

This Python code is designed to determine whether it is possible to complete all the required courses given a set of prerequisites. It uses a topological sorting algorithm to accomplish this. Here’s a brief explanation of the code:

  1. The code defines a Solution class with a canFinish method that takes two parameters: numCourses (the total number of courses) and prerequisites (a list of pairs indicating which course must be taken before another).

  2. It initializes an empty graph as an adjacency list using a defaultdict to represent the courses and their prerequisites. It also initializes a list called in_degree to keep track of the in-degrees of courses, which is used in the topological sorting process.

  3. The code then populates the graph by iterating through the prerequisites list. For each pair (ai, bi), it adds course ai as a neighbor to its prerequisite course bi in the graph and increments the in-degree of course ai.

  4. Next, it initializes a queue with courses that have no prerequisites. It does this by iterating through all the courses and adding those with an in-degree of 0 to the queue.

  5. The code performs a topological sorting of the courses using a while loop. In each iteration of the loop, it dequeues a course from the front of the queue (a course with no prerequisites).

  6. For each neighbor (course that depends on the dequeued course), it decrements the in-degree of the neighbor. If the neighbor’s in-degree becomes 0, it means all of its prerequisites have been taken, so the neighbor is added to the queue.

  7. The loop continues until there are no more courses with no prerequisites to dequeue, and the in-degrees are updated accordingly.

  8. After the loop, if all courses were successfully taken (i.e., numCourses becomes 0), it means that there were no circular dependencies, and it’s possible to finish all courses. In this case, the method returns True. Otherwise, if there are remaining courses (indicating a circular dependency), it returns False.

Test cases:#

Here’s how you can use this solution:

# Example 1
numCourses1 = 2
prerequisites1 = [[1, 0]]
sol = Solution()
print(sol.canFinish(numCourses1, prerequisites1))  # Output: True

True

# Example 2
numCourses2 = 2
prerequisites2 = [[1, 0], [0, 1]]
print(sol.canFinish(numCourses2, prerequisites2))  # Output: False

False

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the canFinish method:

Time Complexity:

  1. Constructing the graph: In the first loop where we iterate through the prerequisites list, we populate the graph with prerequisites. This loop has a time complexity of O(E), where E is the number of prerequisites (edges).

  2. Initializing in-degrees and finding courses with no prerequisites: In the worst case, we iterate through all numCourses courses to initialize in-degrees and find the courses with no prerequisites. This has a time complexity of O(V), where V is the number of courses (vertices).

  3. Topological Sorting: In the while loop, we perform topological sorting, processing each course once and its outgoing edges. In the worst case, each course is processed once. This has a time complexity of O(V + E).

The overall time complexity is O(V + E), where V is the number of courses, and E is the number of prerequisites.

Space Complexity:

  1. Graph Representation: The space complexity for storing the graph as an adjacency list is O(E), where E is the number of prerequisites.

  2. In-Degree Array: The space complexity for storing the in-degrees of courses is O(V), where V is the number of courses.

  3. Queue: The space complexity for the queue is O(V), as it may contain all the courses.

The overall space complexity is O(V + E), where V is the number of courses, and E is the number of prerequisites.

In most practical cases, the number of prerequisites (E) is much smaller than the number of courses (V), so the time and space complexity can often be considered as O(V).

Challenging Exercises:#

  1. Optimizing Course Scheduling: Given a list of courses with their durations and prerequisites, find the most efficient way to schedule these courses to minimize the time it takes to complete all of them.

  2. Detecting Cycles in Course Dependencies: Modify the original problem to not just determine if you can finish all courses but also to identify the specific courses that form a cycle in the prerequisite dependencies.