LeetCode 210: Course Schedule II

Problem Restatement

We are given:

numCourses
prerequisites

Each prerequisite pair:

[a, b]

means:

to take course a, you must first complete course b

We must return a valid order in which all courses can be completed.

If it is impossible because of a cycle, return an empty list.

The official statement says: return any valid ordering of courses that allows completion of all courses. If no ordering exists, return an empty array.

Input and Output

Example function shape:

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    ...

Examples

Example 1:

numCourses = 2
prerequisites = [[1,0]]

Graph:

0 -> 1

Take 0 first, then 1.

Valid answer:

[0, 1]

Example 2:

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Graph:

0 -> 1
0 -> 2
1 -> 3
2 -> 3

Possible valid orders:

[0,1,2,3]

or:

[0,2,1,3]

Both are correct.

Example 3:

numCourses = 2
prerequisites = [[1,0],[0,1]]

Graph:

0 -> 1
1 -> 0

This creates a cycle.

No valid ordering exists.

Answer:

[]

Relationship to LeetCode 207

LeetCode 207 asked:

Can we finish all courses?

LeetCode 210 asks:

What is the actual valid ordering?

The core idea is the same:

• detect cycles
• perform topological sorting

If the graph is acyclic, a topological order exists.

Understanding Topological Order

A topological ordering is an ordering of nodes such that:

every prerequisite appears before its dependent course

Example:

0 -> 1
0 -> 2
1 -> 3
2 -> 3

A valid ordering:

0, 1, 2, 3

because:

• 0 appears before 1
• 0 appears before 2
• 1 appears before 3
• 2 appears before 3

Key Insight

Courses with indegree 0 have no remaining prerequisites.

So:

• they can be taken immediately
• after taking them, we remove their outgoing edges
• this may unlock more courses

This is exactly Kahn’s topological sorting algorithm.

Algorithm (BFS Topological Sort)

1. Build the graph.
2. Compute indegree of every course.
3. Push all indegree 0 courses into a queue.
4. Repeatedly:
   • pop a course
   • append it to the answer
   • reduce indegree of neighbors
   • if a neighbor becomes indegree 0, push it into the queue
5. If all courses were processed, return the ordering.
6. Otherwise return [].

Walkthrough

Use:

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Initial indegrees:

Initial queue:

[0]

Process 0.

Order becomes:

[0]

Reduce indegrees:

Push:

[1, 2]

Process 1.

Order:

[0,1]

Reduce indegree of 3:

2 -> 1

Process 2.

Order:

[0,1,2]

Reduce indegree of 3:

1 -> 0

Push 3.

Process 3.

Final order:

[0,1,2,3]

All courses processed successfully.

Why Cycles Prevent Completion

Suppose:

[[1,0],[0,1]]

Indegrees:

No course has indegree 0.

The queue starts empty.

We cannot begin.

That means no valid ordering exists.

Correctness

The algorithm always selects courses with indegree 0.

A course with indegree 0 has no unmet prerequisites, so placing it next in the ordering is valid.

After removing a course, the algorithm removes all outgoing edges from that course by decrementing neighbor indegrees. This correctly models completing that prerequisite.

If the graph is acyclic, there is always at least one node with indegree 0, so the process continues until every course is added to the ordering.

If the graph contains a cycle, every node in the cycle always depends on another node in the cycle. Therefore none of them can ever reach indegree 0.

In that case, some courses remain unprocessed, and the algorithm returns an empty list.

Thus:

• a returned ordering is always valid
• returning [] correctly indicates that no valid ordering exists

Complexity

Where:

• V = numCourses
• E = number of prerequisite pairs

BFS Topological Sort Implementation

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque()

        for course in range(numCourses):
            if indegree[course] == 0:
                queue.append(course)

        order = []

        while queue:
            current = queue.popleft()
            order.append(current)

            for neighbor in graph[current]:
                indegree[neighbor] -= 1

                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        if len(order) == numCourses:
            return order

        return []

Code Explanation

Build adjacency list:

graph = [[] for _ in range(numCourses)]

Track prerequisites count:

indegree = [0] * numCourses

Build edges:

graph[prereq].append(course)
indegree[course] += 1

Push courses with no prerequisites:

if indegree[course] == 0:
    queue.append(course)

Process courses:

current = queue.popleft()
order.append(current)

Reduce neighbor indegrees:

indegree[neighbor] -= 1

When a course becomes available:

if indegree[neighbor] == 0:
    queue.append(neighbor)

Finally:

if len(order) == numCourses:
    return order

Otherwise a cycle exists:

return []

DFS Topological Sort

We can also solve the problem using DFS.

Idea:

• recursively visit dependencies
• add nodes after exploring neighbors
• reverse the final order

Cycle detection uses three states:

If DFS reaches a node already marked 1, a cycle exists.

DFS Implementation

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]

        for course, prereq in prerequisites:
            graph[prereq].append(course)

        state = [0] * numCourses
        order = []

        def dfs(node):
            if state[node] == 1:
                return False

            if state[node] == 2:
                return True

            state[node] = 1

            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False

            state[node] = 2
            order.append(node)

            return True

        for course in range(numCourses):
            if not dfs(course):
                return []

        return order[::-1]

DFS Explanation

When entering a node:

state[node] = 1

This marks it inside the recursion stack.

If DFS revisits another 1 node, a cycle exists.

After exploring all neighbors:

state[node] = 2

The node is fully processed.

Append the node after exploring dependencies:

order.append(node)

Finally reverse the result:

return order[::-1]

because DFS postorder builds the order backward.

Testing

def is_valid_order(order, numCourses, prerequisites):
    if len(order) != numCourses:
        return False

    position = {}

    for i, course in enumerate(order):
        position[course] = i

    for course, prereq in prerequisites:
        if position[prereq] > position[course]:
            return False

    return True

def run_tests():
    s = Solution()

    order = s.findOrder(2, [[1,0]])
    assert is_valid_order(order, 2, [[1,0]])

    order = s.findOrder(4, [[1,0],[2,0],[3,1],[3,2]])
    assert is_valid_order(order, 4, [[1,0],[2,0],[3,1],[3,2]])

    assert s.findOrder(2, [[1,0],[0,1]]) == []

    order = s.findOrder(1, [])
    assert is_valid_order(order, 1, [])

    order = s.findOrder(3, [[1,0],[2,1]])
    assert is_valid_order(order, 3, [[1,0],[2,1]])

    print("all tests passed")

run_tests()