← DSA Atlas
Dedicated problem page · #210

Course Schedule II

MediumTopological SortEmit nodes in dependency-safe orderTopological sort (Kahn's BFS)
Solve on LeetCode ↗
210
MediumTopological SortTopological sort (Kahn's BFS)Emit nodes in dependency-safe order

Course Schedule II

There are numCourses courses labeled 0..numCourses-1 with prerequisite pairs [a, b] meaning b must precede a. Return any ordering of all courses that respects every prerequisite, or an empty array if no such ordering exists (the graph has a cycle).

Open official problem prompt ↗
In plain English

Produce a concrete schedule of all courses such that every course appears after all of its prerequisites, or prove no such schedule exists.

Picture it like this

Like publishing a build order for software modules: you print a module only once every library it imports has already been printed.

Example
Input
numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output
[0, 1, 2, 3]
Why
0 has no prerequisite; 1 and 2 each need 0; 3 needs both 1 and 2, so it comes last.
Constraints
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= a_i, b_i < numCoursesa_i != b_iAll prerequisite pairs are distinct
Pattern lesson

See the pattern, then code

Emit nodes in dependency-safe order
Recognition clue

The prompt asks for an actual valid ordering (not just yes/no) over 'must come before' constraints, which is the definition of a topological sort output.

↗
Topological Sort

Prerequisites, dependencies, build order, or scheduling over a DAG.. Same peeling as cycle detection, but this time record the order in which courses are removed; that removal order is itself a valid topological order.

New words, made simpleKnow these before the algorithm
Topological order
A node ordering where each directed edge goes from an earlier to a later position.
Frontier
The set of courses currently takeable (in-degree 0).
Cycle
A circular dependency that makes any complete ordering impossible.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
DFS post-order + reverse

Correct but needs explicit cycle coloring and recursion-depth care.

Run DFS, push a node after all its descendants finish, then reverse; abort if a back edge (cycle) is found.

Time O(V + E)Space O(V + E)
Best choiceKahn's algorithm recording pop order

Linear, iterative, and yields the order and the cycle check in one pass.

Peel zero-in-degree nodes and append each to the answer as it is removed.

Time O(V + E)Space O(V + E)
The rule we keep true

Invariant

The order list is a valid topological prefix at all times: every course appended has already had all its prerequisites appended.

Why this is correct

Reasoning

A course is only enqueued when its last prerequisite is removed, so it is always appended after them. If a cycle exists, its members never reach in-degree 0, the order list stays shorter than numCourses, and we correctly return [].

The algorithm in three movesSay these aloud before coding
1Build the graph pre -> course and the in-degree array

indeg = [0, 1, 1, 2]

2Queue all zero-in-degree courses and record each course as it is popped

queue = [0] -> order = [0]; frees 1, 2

3When popping a course, decrement dependents and enqueue any that hit zero

order = [0, 1, 2, 3] (len == 4)

4If the recorded order covers all courses return it, otherwise return [] because a cycle blocked completion

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
22
33
1 · Read[[1,0],[2,0],[3,1],[3,2]]
2 · AskIn-degrees?
3 · Update stategraph: 0->[1,2], 1->[3], 2->[3]; indeg = [0,1,1,2]
4 · ResultOnly 0 starts free.
Key takeaway

Course 0 is emitted first, freeing 1 and 2, which then free 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-8Graph and in-degrees

    Directed edge pre -> course encodes the ordering constraint.

  2. 2
    Lines 9-10Seed and result list

    Start from courses with nothing blocking them.

  3. 3
    Lines 11-18Record pop order

    Appending on pop guarantees prerequisites precede dependents.

  4. 4
    Lines 19Completeness guard

    A short order means a cycle, so return the empty array.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • numCourses = 1 with no prerequisites -> [0]
  • Empty prerequisites -> any permutation, here [0, 1, ..., n-1]
  • A cycle anywhere -> return []
  • Multiple valid orders exist; any correct one is accepted
!

Common beginner mistakes

  • Forgetting the len(order) == numCourses check and returning a partial, invalid order on cyclic input
  • Swapping the meaning of the pair and building course -> pre edges
  • Assuming the answer is unique when the judge accepts any valid topological order
Check your understanding

If several courses sit in the queue at once, does the choice of which to pop first affect correctness?

More in Topological Sort

#207Course ScheduleCycle detection by peeling zero in-degree nodes#269Alien DictionaryDerive edges from adjacent-item comparisons, then topologically sort#310Minimum Height TreesTrim leaves inward until the center remains#329Longest Increasing Path in a MatrixLongest path in an implicit DAG via memoized DFS#1203Sort Items by Groups Respecting DependenciesTwo-level topological sort (order groups, then items within groups)#2050Parallel Courses IIITopological longest path (critical path)