Skip to content

210. Course Schedule II

On LeetCode ->

Problem

Given courses labeled from 0 to numCourses - 1 and prerequisite pairs [course, prerequisite], return any ordering that completes every prerequisite first, or [] if no such ordering exists.

Input:  numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]
State:  0 -> {1, 2} -> 3

Key trick

Use Kahn's topological sort: track each course's number of unmet prerequisites and enqueue it only when that count becomes zero.

Trap

  • Reaching a course from one prerequisite does not make it available; all its prerequisites must be completed.
  • A result containing fewer than numCourses courses means the graph contains a cycle.
  • The pair [a, b] represents the directed edge b -> a, not a -> b.

Why is it interesting?

It reduces dependency scheduling and cycle detection to one linear graph traversal.

Python solution

from collections import deque
from graphlib import CycleError, TopologicalSorter

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

        # A pair [course, prerequisite] creates prerequisite -> course.
        for course, prerequisite in prerequisites:
            graph[prerequisite].append(course)
            indegree[course] += 1

        # Only courses with every prerequisite satisfied are available.
        q = deque(
            course
            for course in range(numCourses)
            if indegree[course] == 0
        )
        res = []

        while q:
            prerequisite = q.popleft()
            res.append(prerequisite)

            for course in graph[prerequisite]:
                indegree[course] -= 1
                if indegree[course] == 0:
                    q.append(course)

        # Any unprocessed course belongs to or depends on a cycle.
        return res if len(res) == numCourses else []

    def findOrder_2(
        self,
        numCourses: int,
        prerequisites: list[list[int]],
    ) -> list[int]:
        graph = {course: set() for course in range(numCourses)}

        for course, prerequisite in prerequisites:
            graph[course].add(prerequisite)

        try:
            return list(TopologicalSorter(graph).static_order())
        except CycleError:
            return []

Time complexity: \(O(V + E)\).

Space complexity: \(O(V + E)\).

Comment on my solution

Your graph direction and initial set of courses without prerequisites are correct, but the traversal marks a course visited after satisfying only one prerequisite.

In the failing case, course 0 is enqueued after processing course 1, even though course 4 is still unmet. A global visited set prevents duplicates but cannot represent how many prerequisites remain; an indegree count is required.

The approach is therefore breadth-first reachability rather than Kahn's algorithm. Kahn's algorithm decrements a course's indegree for every completed prerequisite and enqueues it only when the indegree reaches zero.

# Ideas:
# - I remember the version 1 of this problem using Khan's algo
# - directed graph
# - As we have to return the list of ordered courses
#   - bactracking / DFS while stopping early makes sense
#     - build directed adjacency list
#     - keep a visited set during path construction to avoid cycle
#     - when path length is numCourses return it
#   - implement recursive dfs (if it works, maybe implement
#     iterative version)
# - Maybe BFS with frontiers
#   - start bfs for course with no prerequisites

from collections import deque

# Wrong Answer: 28/47 testcases passed
# 6, [[2,3],[1,2],[0,1],[0,4],[4,5],[5,1]]
# ouptut = [3,2,1,0,5,4]
# expected = [3,2,1,5,4,0]
class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        # 2, [[1,0]] -> [0,1]
        # 4, [[1,0],[2,0],[3,1],[3,2]] -> [0,1,2,3]
        # 1, [] -> [0]
        # 4, [[1,3],[3,1]] -> []
        if not prerequisites:
            return list(range(numCourses))

        graph = [[] for _ in range(numCourses)]
        no_prerequisites = set(range(0, numCourses))
        for a, b in prerequisites:
            graph[b].append(a)
            no_prerequisites.discard(a)

        path = list(no_prerequisites)
        visited = no_prerequisites
        q = deque(no_prerequisites)
        while q:
            b = q.popleft()

            for a in graph[b]:
                if a in visited:
                    continue
                visited.add(a)
                path.append(a)
                q.append(a)
            if len(path) == numCourses:
                return path
        return []