Course Schedule II

Difficulty: Medium

Problem

Same setup as Course Schedule: numCourses courses, and prerequisites[i] = [a, b] meaning take b before a. But now return an actual valid ORDER to take all courses (any valid one). If no order exists (a cycle), return an empty array. You already know the algorithm — this lesson upgrades its output.

Example

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
Explanation: Course 0 first (no prerequisites), then 1 and 2 (both unlocked by 0), then 3 (needs both 1 and 2). [0,2,1,3] would also be valid.

Brute-force approach

No brute-force phase — Kahn's algorithm from the previous lesson is the approach; only the output changes.

Optimal approach

Key insight: The valid order was hiding inside Course Schedule I all along — the sequence in which courses left the queue. Write it down instead of counting it.

Run Kahn's algorithm exactly as in Course Schedule, but append each taken course to an order list. Return the list if complete, else [].

Steps

  1. Build adjacency + indegree (arrow b → a per [a, b])
  2. Seed the queue with all indegree-0 courses
  3. Each dequeued course is APPENDED to the order, then its arrows dissolve
  4. Newly-unblocked courses join the queue
  5. Return order if its length is numCourses, else []

Time complexity: O(V + E) · Space complexity: O(V + E)