MediumDepth-First SearchBreadth-First SearchGraphTopological Sort

Course Schedule II

1 approach, code in every language

There are numCourses courses labeled from 0 to numCourses - 1. You are given a list prerequisites where each entry [a, b] means course b must be completed before course a.

Return any ordering of courses that lets you finish all of them. If more than one valid ordering exists you may return any of them.

If it is impossible to finish every course because of a circular dependency, return an empty array.

Example 1

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

Output: [0,1]

Course 1 depends on course 0, so course 0 must come first. The order [0, 1] finishes both.

Example 2

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

Output: [0,1,2,3]

Course 0 unblocks 1 and 2, and both feed into 3. The order [0, 1, 2, 3] respects every prerequisite (other valid orders exist).

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
All the pairs [a_i, b_i] are distinct.

Kahn's Algorithm (BFS Topological Order)

Emit courses in the order their indegree drops to zero, then verify all courses were placed.

Loading animation…

Intuition

A valid study order is exactly a topological ordering of the prerequisite graph. Any course whose indegree is zero has no unfinished prerequisites, so it is safe to schedule immediately. As we lock a course into the order, we remove its influence by lowering the indegree of the courses it unblocks, which may expose new zero-indegree courses. Appending nodes in the sequence they become free naturally produces a valid ordering. If a cycle exists, its members never reach indegree zero, so the produced order will be shorter than numCourses and we return an empty array.

Algorithm walkthrough

1Build an adjacency list and an indegree array; for each [a, b] add edge b -> a and increment indegree[a].
2Seed a queue with all courses whose indegree is 0.
3Pop a course, append it to the output order, and decrement the indegree of each course it points to.
4Enqueue any course whose indegree just became 0, since it is now free of prerequisites.
5When the queue is empty, check whether the order contains all numCourses entries.
6Return the order if it is complete; otherwise a cycle blocked some courses, so return an empty array.

Implementation

from collections import deque
from typing import List

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(i for i in range(numCourses) if indegree[i] == 0)
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return order if len(order) == numCourses else []

Time

O(V + E)

Space

O(V + E)

V = numCourses, E = prerequisites.length. The order array and queue add O(V) auxiliary space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Module Build Order is our own problem on the technique behind Course Schedule II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free