Compile Ready
Module 4 · Topological Sort

Course Schedule II

MediumProblem 12 of 25 10 min read ~25 min to solve LeetCode
GraphTopological SortBFSDFS
Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Statement

There are numCourses courses labelled 0..numCourses - 1 and a prerequisite list where prerequisites[i] = [course, prerequisite] means prerequisite must be completed before course.

Return any valid order in which all courses can be taken. If no ordering exists because the prerequisite graph has a cycle, return an empty array.

Input

An integer numCourses and directed prerequisite pairs [course, prerequisite]. Each pair means prerequisite must appear before course in the answer.

Output

An int array containing one valid topological ordering, or an empty array if the graph is cyclic.

Constraints

  • •1 <= numCourses <= 2000
  • •0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • •prerequisites[i].length == 2
  • •0 <= course, prerequisite < numCourses
  • •All prerequisite pairs are unique

Examples

Example 1

Input: 
numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: Course 0 has no prerequisites, so it must come before course 1.

Example 2

Input: 
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
Explanation: Course 0 unlocks 1 and 2; both must come before 3. [0,2,1,3] is also valid.

Example 3

Input: 
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []
Explanation: The two courses depend on each other, so no course can appear first in a valid order.

Learning Objectives

  • Turn the Course Schedule feasibility check into an actual topological ordering.
  • Understand why Kahn's pop order is already a valid schedule.
  • Use DFS postorder and reversal to place prerequisites before dependents.
  • Detect cycles while still returning an order only for DAGs.

Intuition

A valid schedule is just a topological ordering: every directed edge points forward in the returned array. If course 0 must precede course 1, then 0 must be placed earlier than 1.

Kahn's algorithm constructs that ordering in the most literal way. At any moment, the zero-indegree courses have no remaining prerequisites, so placing one next cannot violate any dependency. Once it is placed, it may unlock more courses. The order in which courses leave the queue is therefore a valid schedule.

DFS builds the order backward. When DFS finishes a course, it has already finished every course reachable from it, meaning all dependents are already in postorder. Reversing postorder moves prerequisites in front of the courses they unlock. The only blocker is a cycle, which must return an empty array rather than a partial order.

Common mistakes

  • ×Returning the list from DFS postorder without reversing it when edges point prerequisite → course.
  • ×Returning a partial Kahn order even when processed < numCourses. A partial schedule is not a valid answer.
  • ×Treating multiple valid orders as wrong. Any topological order is acceptable.
  • ×Forgetting isolated courses. Courses with no edges still belong in the returned order.
  • ×Using [course, prerequisite] as course → prerequisite and then wondering why the returned order is reversed.

Algorithm Explanation

Kahn's BFS order:

  1. Build graph prerequisite → course and indegree counts.
  2. Enqueue all zero-indegree courses.
  3. Each popped course is appended to the answer immediately because all its prerequisites are already placed.
  4. Decrement dependents' indegrees and enqueue any that reach zero.
  5. If the answer length is numCourses, return it; otherwise return an empty array.

DFS postorder:

  1. Use color states to detect cycles.
  2. DFS every unvisited course.
  3. After exploring all outgoing edges from a course, append the course to postorder.
  4. Reverse postorder to get prerequisites before dependents.
  5. If any DFS sees a gray node, return an empty array.

Solutions

Solution 1: Kahn's BFS collecting pop order

When to prefer this:

Best practical answer for interviews. It is iterative, easy to dry-run, and the queue pop sequence is the topological order itself.

Run the same zero-indegree peeling used in Course Schedule, but write each popped course into the result array. If all courses are popped, the result is a valid ordering.

Step-by-step

  1. Build adjacency and indegree arrays from prerequisites.
  2. Seed a queue with courses whose indegree is 0, including isolated courses.
  3. Pop a course and place it at the next result index.
  4. For each dependent course, decrement indegree and enqueue it when it becomes available.
  5. Return the filled result only if every course was placed.
Time

O(V + E)

Space

O(V + E)

The result, indegree array, queue, and adjacency list are linear in the graph size.

Java implementation

Loading…

Solution 2: DFS postorder then reverse

When to prefer this:

Useful when you prefer recursive dependency reasoning or are already doing DFS cycle detection. It produces the same topological-order guarantee after reversing postorder.

DFS the prerequisite graph with 3-color cycle detection. Append a course after all dependents reachable from it are explored, then read that postorder list backward.

Step-by-step

  1. Build prerequisite → course adjacency.
  2. DFS every unvisited course with colors 0, 1, and 2.
  3. If DFS reaches color 1, a cycle exists and the answer is empty.
  4. Append each course when it turns color 2.
  5. Fill the result array by reading postorder from the end to the beginning.
Time

O(V + E)

Space

O(V + E)

Postorder and color are O(V); recursion stack can also reach O(V).

Java implementation

Loading…

Dry Run

Sample input

Kahn trace for numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]].

StepQueuePlaced courseOrder so farUnlocked courses
Init[0]-[]Course 0 has no prerequisites
1[0]0[0]1 and 2 drop to indegree 0
2[1,2]1[0,1]3 still waits for 2
3[2]2[0,1,2]3 drops to indegree 0
4[3]3[0,1,2,3]All courses placed

Every placed course had all prerequisites already placed. The final order length is 4, so [0,1,2,3] is a valid topological order.

Interview Tips

Clarify that the answer is not unique; this prevents unnecessary sorting or overfitting to one sample output. Kahn's BFS is usually the clearest because the result is exactly the pop order. If presenting DFS, explicitly mention that postorder must be reversed for prerequisite → course edges. Always finish with the cycle condition: return an empty array if you cannot place every course.

Likely follow-ups

  • Return the lexicographically smallest valid order by using a min-heap instead of a queue.
  • Return all valid course orders, or count how many exist.
  • Group courses into semesters where each semester contains all currently available courses.
  • Detect and return one concrete cycle when no order exists.

Similar Problems

Course Schedule
MediumSame graph; only asks whether an order exists.
Alien Dictionary
HardTopological ordering over inferred character constraints.
Parallel Courses
MediumTopological sort counted by BFS layers.
Sequence Reconstruction
MediumTopological sort with uniqueness constraints.

Key Takeaways

  • A valid schedule is a topological order of the prerequisite graph.
  • Kahn's pop order is valid because every popped node has no remaining incoming edges.
  • DFS postorder places dependents first, so reverse it to put prerequisites first.
  • Never return a partial order when a cycle blocks the remaining nodes.
Reusable template: Topological ordering: repeatedly output zero-indegree nodes, or DFS postorder then reverse; reject the graph if a cycle is found.