Course Schedule

You'll use topological sort: repeatedly take a course with nothing left blocking it. If you get stuck, there's a cycle. You need adjacency lists and queues. Related chapter: topological sort and union-find.

1. The problem

Courses are numbered 0 to numCourses - 1. A pair [course, prerequisite] means you must take the prerequisite before the course. Return whether some order lets you take all the courses, including ones with no pairs at all. No pair repeats. Don't change the input. LeetCode 207.

Watch the direction: [1, 0] means 0 comes first.

2. A correct baseline

Try every order, checking each prerequisite's position.

from itertools import permutations

def baseline(num_courses, prerequisites):
    for order in permutations(range(num_courses)):
        position = {course: i for i, course in enumerate(order)}
        if all(position[pre] < position[course] for course, pre in prerequisites):
            return True
    return False

assert baseline(2, [[1, 0]])
assert not baseline(2, [[1, 0], [0, 1]])
assert baseline(3, [])
assert not baseline(1, [[0, 0]])

For V courses and E pairs, this takes up to O(V! · (V + E)) time. With just 12 courses, that's nearly 500 million orders. It uses O(V) extra space.

The bottleneck. It tries orders that are obviously wrong from the first step, such as ones that start with a course whose prerequisite hasn't been taken.

3. The observation

Build an order the way you'd plan a degree. Take any course with no prerequisites left. Taking it may free up other courses. Repeat.

For each course, count its prerequisites not yet taken. Store an arrow from each prerequisite to its course, so taking a course can lower the counts of the courses after it. A queue holds the courses whose count is zero. If the queue runs out before every course is taken, the courses left wait on each other in a cycle. This method is called topological sort.

4. The solution and a trace

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        """Positive course count; unique [course, prerequisite] pairs in range."""
        dependents = [[] for _ in range(numCourses)]
        remaining = [0] * numCourses
        for course, pre in prerequisites:
            dependents[pre].append(course)
            remaining[course] += 1
        # Ready courses have no prerequisites outside the completed set.
        ready = deque(i for i in range(numCourses) if remaining[i] == 0)
        completed = 0
        while ready:
            pre = ready.popleft()
            completed += 1
            for course in dependents[pre]:
                remaining[course] -= 1
                if remaining[course] == 0:
                    ready.append(course)
        return completed == numCourses

solve = Solution().canFinish
assert solve(2, [[1, 0]])
assert not solve(2, [[1, 0], [0, 1]])
assert solve(3, [])
assert not solve(1, [[0, 0]])

Trace 4, [[1,0],[2,0],[3,1],[3,2]]. The counts are listed by course number:

5. Why it works

What stays true. Each course's count is the number of its prerequisites not yet taken.

A True answer is right. A course enters the queue only when all its prerequisites are taken, so the order we take them in works. If we take all V courses, that's a valid order.

A False answer is right. Suppose we get stuck with courses left, each with a count above zero. Pick one, and step to one of its untaken prerequisites. Repeat. There are only so many courses, so you eventually revisit one: that's a cycle. No order can put every course in a cycle after the one before it.

6. Cost, edge cases, and failure

Cost. Each course enters the queue at most once, and each pair is handled once. That's O(V + E) time, growing in step with the courses and pairs. The lists take O(V + E) space.

Edge cases. Courses with no pairs still count toward the total. A cycle anywhere, even among courses unrelated to the rest, makes finishing impossible. The input isn't changed.

Where it fails. Ignoring the arrows' direction would reject valid schedules. Three courses can form a triangle without being a cycle:

# The underlying triangle is cyclic, but its directed dependencies are a DAG.
assert solve(3, [[1, 0], [2, 0], [2, 1]])
assert not solve(4, [[1, 0], [3, 2], [2, 3]])  # A separate cyclic component.

import random
rng = random.Random(207)
for _ in range(350):
    n = rng.randrange(1, 7)
    pairs = [[a, b] for a in range(n) for b in range(n) if rng.randrange(5) == 0]
    before = [pair[:] for pair in pairs]
    assert solve(n, pairs) == baseline(n, pairs)
    assert pairs == before
assert solve(2000, [[i, i - 1] for i in range(1, 2000)])