Course Schedule Solution in Python

Problem Description

Ah, the classic dilemma of college life: you want to graduate, but first, you have to navigate the labyrinth of prerequisites. Imagine you’re trying to get a degree in “Advanced Napping” but first, you need to complete “Intro to Napping” and “Napping Techniques 101.” The problem is, what if your friend, who is also your professor, decided to throw in a few extra courses that you need to take before you can even think about napping?

In the LeetCode problem “Course Schedule,” you are given a number of courses and a list of prerequisite pairs. Your task is to determine if you can finish all the courses without getting stuck in an endless loop of prerequisites. Spoiler alert: if you can’t, you might just end up with a degree in “Procrastination.”

Code Solution


from enum import Enum

class State(Enum):
    kInit = 0
    kVisiting = 1
    kVisited = 2

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        states = [State.kInit] * numCourses

        for v, u in prerequisites:
            graph[u].append(v)

        def hasCycle(u: int) -> bool:
            if states[u] == State.kVisiting:
                return True
            if states[u] == State.kVisited:
                return False

            states[u] = State.kVisiting
            if any(hasCycle(v) for v in graph[u]):
                return True
            states[u] = State.kVisited

            return False

        return not any(hasCycle(i) for i in range(numCourses))

Approach

The approach taken in this solution is akin to a detective trying to solve a mystery. We build a directed graph where each course is a node, and the prerequisites are directed edges. We then perform a depth-first search (DFS) to check for cycles. If we encounter a node that is currently being visited, we have a cycle, and thus, it’s impossible to finish all courses. If we finish visiting a node, we mark it as visited.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(V + E)
Space Complexity	O(V)

Real-World Example

Let’s say you want to become a chef, but first, you need to take “Basic Cooking” and “Knife Skills.” However, your culinary school has a rule: you can’t take “Advanced Cooking” until you’ve completed “Basic Cooking.” If you find yourself in a situation where you need to take “Advanced Cooking” before “Basic Cooking,” you’re in a pickle (pun intended). This problem is a perfect representation of that scenario!