Course Schedule II

PracticeNeetCode ↗LeetCode ↗

Same setup as Course Schedule, but return one valid order to take all numCourses courses given the prerequisite pairs. If no valid order exists, return an empty array.

Example

Key Pointers

• Same cycle detection as Course Schedule, plus recording a valid topological order along the way.
• Post-order DFS — appending a course only after all its prerequisites are fully processed — naturally produces a valid ordering.
• If a cycle turns up anywhere, no valid ordering exists at all — return an empty list immediately.

Step-by-Step Analysis

1. Build the adjacency list of course → prerequisites, plus visiting and visited sets as in Course Schedule.
2. DFS(course): if visiting, return False (cycle). If visited, return True. Otherwise mark visiting, recurse into every prerequisite, then mark visited, append the course to the result list, and return True.
3. Run DFS across every course; if any call returns False, return [] immediately.
4. Otherwise return the result list — prerequisites were appended before the courses depending on them, so it's already a valid order.

Complexity

Time: O(V + E) — Space: O(V + E)

Code

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = {i: [] for i in range(numCourses)}
    for course, pre in prerequisites:
        graph[course].append(pre)

    visiting, visited = set(), set()
    order = []

    def dfs(course: int) -> bool:
        if course in visiting:
            return False
        if course in visited:
            return True

        visiting.add(course)
        for pre in graph[course]:
            if not dfs(pre):
                return False
        visiting.remove(course)
        visited.add(course)
        order.append(course)
        return True

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

    return order

Code Explanation

How the solution above works, piece by piece.

1. Same graph and cycle detection as Course Schedule: graph[course] lists prerequisites.
2. The only addition: when a course's DFS finishes (all its prerequisites done), append it to order.
3. Because edges point to prerequisites, a course is always appended after everything it depends on, which is exactly a valid order to take them.
4. If any DFS finds a cycle, no order exists → return [].
5. O(V + E) time and space.

Visual Walkthrough

Running it on numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]:

Video Explanation

NeetCode — Course Schedule II, LeetCode 210