190. Course Schedule II
Same university as before: num_courses courses labeled 0 through num_courses - 1, and a list prerequisites where the pair [a, b] means course b must be passed before course a. This time, don't just say whether the schedule is feasible — produce an actual order to take the courses in.
Your function receives num_courses and prerequisites and returns a list of all num_courses labels in a valid order: every course appears after all of its prerequisites. To make the answer unique, whenever more than one course is currently takeable, take the one with the smallest label first — that is, return the lexicographically smallest valid order. If the requirements form a cycle so that no valid order exists, return an empty list; the raw output prints -1 in that case.
Example 1:
Input: num_courses = 2, prerequisites = [[1, 0]]
Output: [0, 1]
Explanation: Course 1 waits on course 0, so the only possible order is 0 then 1.
Example 2:
Input: num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]
Explanation: After 0, both 1 and 2 are takeable; the smallest-label rule picks 1, then 2, and 3 last. [0, 2, 1, 3] is also valid but not lexicographically smallest.
Example 3:
Input: num_courses = 2, prerequisites = [[1, 0], [0, 1]]
Output: []
Explanation: The two courses require each other, so no order can ever start.
Constraints:
- 1 ≤ num_courses ≤ 2000
- 0 ≤ prerequisites.length ≤ 5000
- 0 ≤ a, b < num_courses
- Pairs may repeat, and a pair may name the same course twice (which makes the schedule impossible).
- Among all valid orders, output the lexicographically smallest one; output -1 when none exists.
Hints:
This is topological sorting: courses are nodes, each pair [a, b] is an edge b → a, and you must list nodes so that every edge points forward.
Kahn's algorithm builds the order directly: keep every course whose remaining prerequisite count (indegree) is 0 in a container, repeatedly take one out, append it, and decrement the indegree of the courses it unlocks. If you finish with fewer than n courses, a cycle blocked the rest.
A plain FIFO queue yields *a* valid order, but not necessarily the lexicographically smallest one. Swap the queue for a min-heap so the smallest takeable label always comes out first.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: num_courses = 2, prerequisites = [[1, 0]]
Expected output: [0, 1]