Course Schedule II

There are numCourses courses numbered from:

0 to numCourses - 1

You are given prerequisite pairs:

[a, b]

which means:

You must complete course b before taking course a.

Return an ordering of courses that allows you to finish all courses.

If it is impossible because of a cycle, return an empty array.

Example

numCourses = 4

prerequisites:

[1,0]

[2,0]

[3,1]

[3,2]

The dependencies are:

0 → 1

0 → 2

1 → 3

2 → 3

One valid order is:

0 1 2 3

Another valid order is:

0 2 1 3

Both are correct.

Main Idea

This is a Topological Sort problem.

We can use Kahn's Algorithm (BFS):

1. Build the directed graph.
2. Calculate the indegree of every course.
3. Add all courses with indegree 0 to a queue.
4. Remove courses one by one.
5. Reduce the indegree of their neighboring courses.
6. Whenever a course becomes 0, add it to the queue.
7. If all courses are processed, return the ordering.
8. Otherwise, a cycle exists → return empty array.