Course Schedule

The problem description can be found in LeetCode.

Approach

This is a typical problem where we can apply Topological Sorting algorithm. In particular, if a topological ordering is possible it means that the student can finish all the courses.

Moreover, we can also notice that the input is not a Graph, but we can easily build an Adjacency List.

Solution

from collections import deque
from typing import Deque, Dict, List


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = self.get_adjacency_list(numCourses, prerequisites)
        in_degree = self.get_in_degree(graph)

        queue: Deque[int] = deque()
        for course, degree in in_degree.items():
            if degree == 0:
                queue.append(course)

        num_checked_courses = 0
        while queue:
            course = queue.popleft()
            num_checked_courses += 1
            for dep_course in graph[course]:
                in_degree[dep_course] -= 1
                if in_degree[dep_course] == 0:
                    queue.append(dep_course)

        return num_checked_courses == numCourses

    def get_adjacency_list(
        self, numCourses: int, prerequisites: List[List[int]]
    ) -> Dict[int, List[int]]:
        graph: Dict[int, List[int]] = {course: [] for course in range(numCourses)}

        for a, b in prerequisites:
            graph[b].append(a)

        return graph

    def get_in_degree(self, graph: Dict[int, List[int]]) -> Dict[int, int]:
        in_degree: Dict[int, int] = {course: 0 for course in range(len(graph))}

        for course_preqs in graph.values():
            for course in course_preqs:
                in_degree[course] += 1

        return in_degree

Complexity

• Time: $O(numCourses+p)$
• Space: $O(numCourses+p)$

Where $p$ is the size of the prerequisites list.