Course Schedule II

35 min · findOrder()

Knowing that a degree is possible isn't enough; you still need the semester-by-semester plan.

You're given numCourses courses labeled from 0 through numCourses - 1 and a list prerequisites. A pair [course, prerequisite] means prerequisite must appear before course in your answer.

Return a topological order — a list that places every directed dependency before the course that relies on it. If a cycle — a dependency chain that leads back to its starting course — makes such an order impossible, return [].

Every solvable judged input has exactly one valid order. That makes the requested output deterministic: you never need to choose between two equally valid schedules.

Constraints

1 <= numCourses <= 2_000
0 <= prerequisites.length <= 5_000
Every pair contains two course labels in the range 0..numCourses - 1.
Prerequisite pairs are distinct, and no course is its own prerequisite.
Every acyclic input has a unique topological order.

Hints

Start with what is ready

Count each course's incoming prerequisite edges. A course with in-degree zero can safely go next because nothing unfinished blocks it.

Remove completed work

After adding a ready course to the answer, reduce the in-degree of every course that depends on it. A count that reaches zero reveals the next ready course.

Recognize a cycle

If the ready queue becomes empty before your answer contains all courses, the remaining courses depend on one another in a cycle. Return an empty array.

Follow-up

How would you detect whether an arbitrary acyclic graph has one topological order or several? Watch the size of the ready frontier at each step.

Visible cases

Examples

Example 1

ready

Input: numCourses = 2 prerequisites = [ [ 1, 0 ] ]
Expected: [ 0, 1 ]
Why: course 0 unlocks course 1

Example 2

ready

Input: numCourses = 4 prerequisites = [ [ 1, 0 ], [ 2, 1 ], [ 3, 2 ], [ 2, 0 ], [ 3, 1 ] ]
Expected: [ 0, 1, 2, 3 ]
Why: the consecutive dependencies force one order

Example 3

ready

Input: numCourses = 1 prerequisites = []
Expected: [ 0 ]
Why: the only course is the whole schedule

Interview signal

Asked at

AmazonGoogleMeta

DFS post-order — finish dependents first, then reverse

A DFS cycle check gives each course one of three states: unvisited, active on the current path, or finished. Reaching an active course means a cycle, so return [].

When a course has no unexplored dependents left, append it to post_order. That list has courses before their prerequisites, so reverse it once at the end. The explicit stack avoids Python's recursion-depth limit on a 2,000-course chain.

def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = [[] for _ in range(num_courses)]
    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
 
    color = [0] * num_courses
    post_order = []
    for start in range(num_courses):
        if color[start] != 0:
            continue
 
        color[start] = 1
        stack = [(start, 0)]
        while stack:
            course, next_index = stack[-1]
            if next_index == len(graph[course]):
                color[course] = 2
                post_order.append(course)
                stack.pop()
                continue
 
            next_course = graph[course][next_index]
            stack[-1] = (course, next_index + 1)
            if color[next_course] == 1:
                return []
            if color[next_course] == 0:
                color[next_course] = 1
                stack.append((next_course, 0))
 
    return post_order[::-1]

Time O(V + E), space O(V + E) for the graph, state array, output, and DFS stack.

Kahn's topological sort — write the order as courses become ready

Kahn's topological sort tracks each course's in-degree, the number of prerequisites that still block it. Put every zero-in-degree course into a queue, take one, append it to the order, and remove its outgoing dependencies.

from collections import deque
 
 
def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses
    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        in_degree[course] += 1
 
    ready = deque(
        course for course in range(num_courses) if in_degree[course] == 0
    )
    order = []
    while ready:
        course = ready.popleft()
        order.append(course)
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                ready.append(next_course)
 
    if len(order) != num_courses:
        return []
    return order

A cycle eventually empties the queue while some courses remain blocked. On every solvable test here, the ready frontier contains exactly one course at each step, which is the defining signal that the topological order is unique.

Time O(V + E), space O(V + E) for the graph, in-degree array, queue, and result.

DFS writes the answer backward as searches finish. Kahn's algorithm writes it forward as prerequisites disappear. The unique-order guarantee makes both results identical.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraynumCourses: int · prerequisites: int[][]

Expected

[
  0,
  1
]

Run: visible + custom · Submit: full suite