This time, return an actual order in which all courses can be taken. If no order exists, return an empty array.
DSA Animator › DSA Revision › Graph › Course Schedule II
Remember: the order in which Kahn’s queue releases courses is a topological order. A short result means a cycle. The video solves Course Schedule II (LeetCode 210, Medium) with the Topological Sort pattern from the Graph topic, and you can replay every step in the interactive Course Schedule II animation.
This time, return an actual order in which all courses can be taken. If no order exists, return an empty array.
For 4 courses with pairs 1 0, 2 0, 3 1 and 3 2, one valid order is 0, 1, 2, 3. Another valid order is 0, 2, 1, 3, because any order that respects the arrows is accepted.
Generating permutations and checking each one is far too slow. Kahn’s algorithm already produces an order as a side effect.
Run the same in degree process as in Course Schedule. Every time a course leaves the queue, append it to the answer. A course only enters the queue after all its prerequisites have left it. So the answer list is automatically a valid order. If the list is shorter than the number of courses, there was a cycle, so return an empty array.
Course 0 has in degree 0, so the queue starts with 0. Take 0, and the order is 0, while courses 1 and 2 become free. Take 1, and the order is 0, 1. Take 2, and course 3 becomes free. Take 3, and the order is 0, 1, 2, 3. All four courses are in the order, so it is returned.
In code, compute in degrees and the adjacency list. Queue every course with in degree 0. Each time you poll, write the course into the result array at the next index. Return the array if the index reached the number of courses, otherwise an empty array. It's O of courses plus pairs.
Remember: the order in which Kahn’s queue releases courses is a topological order. A short result means a cycle.