Course Schedule Ordering

Find a valid order to take all courses given prerequisites.

graph topological-sort bfs course-schedule

You are given `num_courses` and a list of prerequisite pairs `prerequisites`. Each pair `[a, b]` means that course `b` must be taken before course `a`. Return a list of courses in a valid order such that all prerequisites are satisfied. If it is impossible, return an empty list.

Implement the function `find_order(num_courses: int, prerequisites: List[List[int]]) -> List[int]`.

- Courses are labeled from `0` to `num_courses - 1`.
- Each prerequisite pair is `[course, prerequisite]`.
- If multiple valid orders exist, any one is accepted.
- If there is a cycle, return `[]`.

Your solution should handle up to 2000 courses and 5000 prerequisites efficiently.

Constraints

- `1 <= num_courses <= 2000`
- `0 <= len(prerequisites) <= 5000`
- Each pair contains integers in `[0, num_courses-1]`.
- No duplicate prerequisite pairs? (The statement doesn't specify, but your solution should still handle duplicates gracefully.)
- Time complexity: O(V + E).

Example

```python
find_order(2, [[1, 0]])
# Output: [0, 1]

find_order(4, [[1,0],[2,0],[3,1],[3,2]])
# Output: [0, 2, 1, 3] or any valid order

find_order(2, [[0,1],[1,0]])
# Output: []

find_order(1, [])
# Output: [0]
```

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the courses as nodes and prerequisites as directed edges.

A course can be taken when all its prerequisites have been taken — this is a topological ordering.

Use Kahn's algorithm: repeatedly remove nodes with in-degree zero.

If you cannot process all nodes, there is a cycle.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.