Given numCourses and a list of prerequisite pairs [a, b] meaning you must take b before a, return an ordering of all courses that satisfies every prerequisite. Return an empty array if no valid ordering exists.
Example 1
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] (or [0,2,1,3])
Explanation: Course 0 has no prerequisites; 1 and 2 depend on 0; 3 depends on both 1 and 2.
1 <= numCourses <= 20000 <= prerequisites.length <= 5000This is Course Schedule (does a valid order exist) plus one requirement: return the order itself, not just yes/no.
Kahn's algorithm (BFS-based topological sort) naturally produces the order as a side effect of the process — track it as you go.
The same 'is there a cycle' detection from Course Schedule falls out for free here: if you can't place all N courses, a cycle exists.
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]); // p[1] -> p[0]
inDegree[p[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.offer(i);
int[] order = new int[numCourses];
int index = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
order[index++] = course;
for (int next : graph.get(course)) {
if (--inDegree[next] == 0) queue.offer(next);
}
}
return index == numCourses ? order : new int[0]; // fewer than numCourses placed means a cycle exists
}Time: O(V + E) · Space: O(V + E)