Course Schedule

Problem

https://leetcode.com/problems/course-schedule/

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] = [a:sub:`i`, b:sub:`i`] indicates that you must take course b:sub:`i` first if you want to take course a:sub:`i`.

• 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 <= a:sub:`i`, b:sub:`i`< numCourses

• All the pairs prerequisites[i] are unique.

Pattern

Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Approaches

Topological Sort

Explanation

If the courses can be finished, we will be able to use topological sort to produce a valid course path. First, convert the list of prerequisites from an edge list into an adjacency list while also tracking the in degree of each node in a dictionary in_degree (the number of remaining prereqs). We can only start a course when all its prereqs are finished, i.e. in-degree = 0. We add these to a queue. As we take each course by popping from the queue, we reduce the in-degree of the downstream courses by 1. If those courses reach and in-degree of 0, then we add them to the queue.

If the set of taken courses contains all courses, then it is possible to finish the courses. Otherwise, it is not.

Code

from collections import defaultdict, deque


def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    """Return whether it is possible to finish all courses given the list of
    ``prerequesites``.
    """
    graph = defaultdict(list)
    in_degrees = defaultdict(int)

    for [a, b] in prerequisites:
        graph[b].append(a)
        graph[a]
        in_degrees[a] += 1
        in_degrees[b]

    queue = deque()
    for node, in_degree in in_degrees.items():
        if in_degree == 0:
            queue.append(node)

    courses = set()
    while queue:
        node = queue.popleft()
        courses.add(node)

        for neighbor in graph[node]:
            in_degrees[neighbor] -= 1
            if in_degrees[neighbor] == 0:
                queue.append(neighbor)

    if len(courses) == len(graph):
        return True
    else:
        return False

Test

>>> from course_schedule__topological_sort import canFinish
>>> canFinish(2, [[1, 0]])
True
>>> canFinish(2, [[1, 0], [0, 1]])
False

Complexity

\(V\) is the number of courses and \(E\) is the length of prerequisites.

Measure	Complexity	Notes
Time	\(O(V + E)\)	every edge and vertex is visited once
Auxiliary Space	\(O(V + E)\)	we create a graph dictionary which stores all the edges and a taken courses array which stores all the courses

course_schedule__topological_sort.canFinish(numCourses: int, prerequisites: list[list[int]]) → bool

Return whether it is possible to finish all courses given the list of prerequesites.