DSA Course Schedule II

The problem

Course Schedule II returns a full course order instead of a yes or no answer. The order must place every course after all of its prerequisites.

Many orders can be valid for one plan, and any one of them is a correct answer. An impossible plan returns an empty list. A cycle is what makes a plan impossible.

cases = [
    (4, [(1, 0), (2, 0), (3, 1), (3, 2)], [0, 1, 2, 3]),
    (6, [(2, 0), (2, 1), (3, 2), (4, 2), (5, 3), (5, 4)], [0, 1, 2, 3, 4, 5]),
    (3, [(1, 0), (2, 1), (0, 2)], []),
    (1, [], [0]),
]
for num, pairs, expected in cases:
    print("courses", num, "pairs", pairs, "->", expected)

The orders printed here are the ones this article produces, with ties broken by course number. Another valid order for the first plan is 0, 2, 1, 3. The checker in the next section accepts both.

Intuition: numeric order is a guess, and guesses fail

The first idea is to trust the numbering and take the courses in order. Numbering carries no promise about prerequisites. A low-numbered course can easily depend on a high-numbered one.

Before building anything clever, the article needs a checker. A checker reads an order and tests every pair against the positions in that order. It also exposes the numeric guess as a guess.

def is_valid(order, pairs):
    pos = {course: i for i, course in enumerate(order)}
    for course, prereq in pairs:
        if pos[prereq] > pos[course]:
            return False
    return True

pairs = [(0, 1)]
print("order [0, 1] valid:", is_valid([0, 1], pairs))
print("order [1, 0] valid:", is_valid([1, 0], pairs))
print("order [0, 2, 1, 3] valid for the first plan:", is_valid([0, 2, 1, 3], [(1, 0), (2, 0), (3, 1), (3, 2)]))

Course 0 needs course 1 in this small plan, so the numeric order fails its only pair. The checker needs no search at all. That gap between checking and finding is the shape of the whole problem.

Brute force: try orderings until one passes the checker

The brute force generates orderings and runs the checker on each one. The first ordering that passes is the answer. If every ordering fails, the plan is impossible and the answer is empty.

The count of orderings is the problem. Four courses have 24 orderings, and each new course multiplies the count by the new course total. A reversed chain is the worst case, because its only valid ordering sits last in the generated sequence.

from itertools import permutations

def is_valid(order, pairs):
    pos = {course: i for i, course in enumerate(order)}
    for course, prereq in pairs:
        if pos[prereq] > pos[course]:
            return False
    return True

def find_order_brute(num_courses, pairs):
    tried = 0
    for order in permutations(range(num_courses)):
        tried += 1
        if is_valid(order, pairs):
            return list(order), tried
    return [], tried

order, tried = find_order_brute(4, [(0, 1), (1, 2), (2, 3)])
print("reversed chain order:", order, "- orderings tried:", tried)
order, tried = find_order_brute(3, [(1, 0), (2, 1), (0, 2)])
print("cycle order:", order, "- orderings tried:", tried)

The reversed chain burns all 24 orderings to find the single working one. The cycle burns all 6 and finds nothing. Both runs are tiny, and both already show a count that explodes with the course total.

The optimal solution: free one course at a time, by indegree

An indegree is the count of prerequisites a course is still waiting on. The method holds a queue of courses whose indegree is zero, takes one out as the next course in the order, and lowers the indegree of every course it frees.

A course enters the queue at the moment its last prerequisite is taken. A plan with a cycle strands its cycle courses above zero forever, so the built order ends short. A short order is reported as the empty list.

from collections import deque


def find_order(num_courses, pairs):
    graph = {i: [] for i in range(num_courses)}
    indegree = {i: 0 for i in range(num_courses)}
    for course, prereq in pairs:
        graph[prereq].append(course)
        indegree[course] += 1
    for v in graph:
        graph[v] = sorted(graph[v])
    queue = deque(sorted(v for v in indegree if indegree[v] == 0))
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            indegree[nb] -= 1
            if indegree[nb] == 0:
                queue.append(nb)
    if len(order) != num_courses:
        return []
    return order

cases = [
    (4, [(1, 0), (2, 0), (3, 1), (3, 2)], [0, 1, 2, 3]),
    (6, [(2, 0), (2, 1), (3, 2), (4, 2), (5, 3), (5, 4)], [0, 1, 2, 3, 4, 5]),
    (3, [(1, 0), (2, 1), (0, 2)], []),
    (1, [], [0]),
]
for num, pairs, expected in cases:
    result = find_order(num, pairs)
    print("courses", num, "->", result, "| expected:", expected, "| match:", result == expected)

All four cases from the start of the article pass. Sorted starts and sorted neighbours fix which valid order prints, so the method is deterministic. The cycle check costs one length comparison at the end.

Walkthrough: freeing the four-course plan

The walk starts with indegrees read off the pairs. Course 0 waits on nothing, courses 1 and 2 wait on course 0, and course 3 waits on both. Each step takes the front course off the queue and prints what it frees.

from collections import deque

pairs = [(1, 0), (2, 0), (3, 1), (3, 2)]
graph = {i: [] for i in range(4)}
indegree = {i: 0 for i in range(4)}
for course, prereq in pairs:
    graph[prereq].append(course)
    indegree[course] += 1
for v in graph:
    graph[v] = sorted(graph[v])
print("indegrees at start:", [(v, indegree[v]) for v in sorted(indegree)])
queue = deque(sorted(v for v in indegree if indegree[v] == 0))
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    freed = []
    for nb in graph[node]:
        indegree[nb] -= 1
        if indegree[nb] == 0:
            queue.append(nb)
            freed.append(nb)
    print("take", node, "- order", order, "- freed", freed, "- queue", list(queue))
print("final order:", order)

Taking course 0 frees both of its followers at once. Course 3 needs two frees, and the second one lands when course 2 is taken. The order is read straight off the take lines.

Complexity

The indegree method takes each course once and lowers one indegree per pair, so its time is proportional to the courses plus the pairs, written O(V + E). Its extra space is the graph, the indegrees and the queue, each proportional to the plan size.

import math
from collections import deque

def edge_steps(num_courses, pairs):
    graph = {i: [] for i in range(num_courses)}
    indegree = {i: 0 for i in range(num_courses)}
    for course, prereq in pairs:
        graph[prereq].append(course)
        indegree[course] += 1
    queue = deque(sorted(v for v in indegree if indegree[v] == 0))
    steps = 0
    done = 0
    while queue:
        node = queue.popleft()
        done += 1
        for nb in graph[node]:
            indegree[nb] -= 1
            steps += 1
            if indegree[nb] == 0:
                queue.append(nb)
    return steps

for n in [4, 6, 8]:
    pairs = [(i, i - 1) for i in range(1, n)]
    print("chain of", n, "- indegree edge steps:", edge_steps(n, pairs), "- orderings a brute search may try:", math.factorial(n))

The edge step count grows by two when the chain grows by two courses. The ordering count multiplies instead. At eight courses the counts are 7 steps against 40320 orderings.

Edge cases and pitfalls

Zero courses return an empty list, and that empty list is a valid order here. The same output means impossible for any positive course count. Reading the empty list without checking the course count is the classic pitfall in this problem.

A duplicate pair is counted twice in the indegree and also appears twice in the graph. The two effects cancel during the walk, so the order still comes out right. A self prerequisite never reaches zero and strands its course, exactly like a larger cycle.

from collections import deque


def find_order(num_courses, pairs):
    graph = {i: [] for i in range(num_courses)}
    indegree = {i: 0 for i in range(num_courses)}
    for course, prereq in pairs:
        graph[prereq].append(course)
        indegree[course] += 1
    for v in graph:
        graph[v] = sorted(graph[v])
    queue = deque(sorted(v for v in indegree if indegree[v] == 0))
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            indegree[nb] -= 1
            if indegree[nb] == 0:
                queue.append(nb)
    if len(order) != num_courses:
        return []
    return order

print("zero courses:", find_order(0, []))
print("self prerequisite:", find_order(1, [(0, 0)]))
print("duplicate pair:", find_order(2, [(1, 0), (1, 0)]))
print("one pair among three courses:", find_order(3, [(1, 0)]))

The last plan shows the tie rule at work. Courses 0 and 2 both start free, and the sorted queue takes 0 first, then 2, then the freed course 1. The order 0, 2, 1 is valid, and the checker from section 2 would accept it.