Find a valid course order from prerequisites

Problem Statement

There are n courses labeled from 0 to n-1. Some courses have prerequisites, where taking course a requires you to have first completed course b. This is represented as a pair [a, b].

Given the total number of courses n and an array of prerequisite pairs, return any valid ordering of courses that you should take to finish all courses. If it is impossible to finish all courses (i.e., there is a cyclic dependency), return an empty list.

Function Signature

def find_course_order(n: int, prerequisites: List[List[int]]) -> List[int]:

Constraints

• 1 <= n <= 2000
• 0 <= len(prerequisites) <= n * (n - 1) / 2
• All prerequisite pairs are unique.

Examples

Example 1: Input: n = 2, prerequisites = [[1, 0]] Output: [0, 1] Explanation: To take course 1, you must finish course 0. So the order is 0 -> 1.

Example 2: Input: n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] Output: [0, 1, 2, 3] (or [0, 2, 1, 3]) Explanation: Course 0 must be taken before 1 and 2. Both 1 and 2 must be taken before 3.

Edge Cases

• No prerequisites: Any order (e.g., [0, 1, 2, ... n-1]) is valid.
• Cyclic dependencies: A -> B -> A; should return an empty list.
• Disconnected components: Multiple independent groups of courses.