Course Schedule II

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    There are n courses labelled 0 to n − 1 and a list of pairs [course, pre], meaning pre must be taken before course. Return any order in which all courses can be taken, or an empty list if that is impossible. A common second part: if you may take any number of courses in one semester as long as their prerequisites were finished in earlier semesters, what is the minimum number of semesters?

    This is the "give me the order" version of Course Schedule, and the standard way interviewers check that you know topological sort rather than just cycle detection. The same code orders build steps, database migrations, spreadsheet cells and package installs. Original problem: LeetCode 210; the semesters version is LeetCode 1136.

    Example

    Six courses: 0 comes first, 1 and 2 need 0, 3 needs both 1 and 2, 4 needs 3 and 5 needs 2. Several orders are valid.
    Six courses: 0 comes first, 1 and 2 need 0, 3 needs both 1 and 2, 4 needs 3 and 5 needs 2. Several orders are valid.
    Input:  n = 6, prerequisites = [[1,0], [2,0], [3,1], [3,2], [4,3], [5,2]]
    Output: [0, 1, 2, 3, 5, 4]       # any valid order is accepted
    Minimum semesters: 4             # {0}, {1, 2}, {3, 5}, {4}
    Input:  n = 4, prerequisites = [[1,0], [2,1], [3,2], [1,3]]
    Output: []                       # 1 -> 2 -> 3 -> 1 is a cycle

    Constraints (assumed)

    • 1 ≤ n ≤ 2,000; up to n × (n − 1) prerequisite pairs, no duplicates.
    • A course never lists itself.

    What this question tests

    • Modelling the input as a directed graph with the edges pointing the right way.
    • Topological sort (Kahn's algorithm or DFS post-order) and how it detects a cycle.
    • Adapting the same loop to a level-by-level answer (semesters) without starting over.

    Questions to ask first

    1. What does [a, b] mean: a before b, or b before a? Getting this backwards still produces an order, just the reversed one. (Here: b before a.)
    2. Any valid order, or a specific one (for example the smallest label first)? (Here: any. Smallest first needs a min-heap instead of a queue.)
    3. What should a cycle return? (Here: an empty list.)
    4. Is there a limit on courses per semester? (Here: no. With a limit k the problem becomes much harder.)