Return one valid order to finish all courses given prerequisite dependencies, or an empty array if no such order exists.
Problem
You are given numCourses labeled from 0 to numCourses - 1 and a list of prerequisite pairs. Each pair [a, b] means that to take course a, you must first complete course b.
Your task is to determine an order in which you can complete all courses so that every prerequisite is satisfied. If multiple valid orders exist, return any one of them. If it is impossible to finish all courses because the dependency graph contains a cycle, return an empty array.
This is a classic dependency-ordering problem on a directed graph.
Input Format
- An integer
numCourses. - A list of prerequisite pairs
prerequisites, where each pair[a, b]indicates a directed edgeb -> a.
Interpretation
- Course
bmust appear before courseain the final ordering. - Courses with no prerequisites may appear anywhere before their dependents.
Output Format
- Return an array of length
numCoursescontaining a valid course order. - If no valid ordering exists, return an empty array
[].
Constraints
0 <= numCourses- Each prerequisite relation is a pair of valid course indices.
- The graph may contain cycles.
- Any valid topological ordering is accepted.
Example 1
Input
numCourses = 2 prerequisites = [[1,0]]
Output
[0,1]
Explanation
Course 0 must be taken before course 1, so a valid order is [0, 1].
Example 2
Input
numCourses = 4 prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output
[0,1,2,3]
Explanation
Course 0 must come before 1 and 2, and both 1 and 2 must come before 3. One valid order is [0, 1, 2, 3].
Show 1 more example
Example 3
Input
numCourses = 2 prerequisites = [[0,1],[1,0]]
Output
[]
Explanation
The two courses depend on each other, so no valid ordering exists.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.