The problem. Same courses and prerequisites as Course Schedule — [course, pre] means take pre first — but now return an order in which you can take all of them. If there are several, any one is fine. If it's impossible, return an empty array.
numCourses = 2, prerequisites = [[1,0]] -> [0,1]
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] -> [0,1,2,3] (or [0,2,1,3])
numCourses = 2, prerequisites = [[1,0],[0,1]] -> []Course Schedule asked is there an order? Both of its fast answers find one along the way, so this lesson is about keeping it.
Kahn's algorithm takes courses in a valid order already: write each one down as it leaves the queue. DFS does it backwards. A course can only finish after every course it unlocks has finished, so the finishing order is a valid schedule reversed. Either way, if some course is never placed, there's a cycle and the answer is empty.
Exactly the Course Schedule code, with an order list in place of the counter.
function findOrder(numCourses, prerequisites) { const next = Array.from({ length: numCourses }, () => []); const indegree = new Array(numCourses).fill(0); for (const [course, pre] of prerequisites) { next[pre].push(course); indegree[course]++; } const order = []; for (let c = 0; c < numCourses; c++) { if (indegree[c] === 0) order.push(c); // ready now } for (let head = 0; head < order.length; head++) { // the order list is the queue for (const d of next[order[head]]) { indegree[d]--; if (indegree[d] === 0) order.push(d); // all of d's prerequisites are placed } } return order.length === numCourses ? order : []; // a short list means a cycle}Time O(V + E), space O(V + E). Each course is placed once and each arrow is used once. A neat detail: the answer list doubles as the queue, with head marking the next course to process.
Run the three-state DFS from Course Schedule. When a course finishes — everything it unlocks is done — push it onto finished. Courses that unlock nothing finish first and the starting courses finish last, so reversing the list gives a valid order.
A course finishes only after everything it unlocks; reverse the finishing list at the end.
function findOrder(numCourses, prerequisites) { const next = Array.from({ length: numCourses }, () => []); for (const [course, pre] of prerequisites) next[pre].push(course); const state = new Array(numCourses).fill(0); // 0 = new, 1 = on the current path, 2 = done const finished = []; // each course lands after all it unlocks const visit = (c) => { if (state[c] === 1) return false; // back onto the current path: a cycle if (state[c] === 2) return true; // already placed state[c] = 1; for (const d of next[c]) { if (!visit(d)) return false; } state[c] = 2; finished.push(c); // everything c unlocks is already placed return true; }; for (let c = 0; c < numCourses; c++) { if (!visit(c)) return []; } return finished.reverse(); // last to finish = first to take}Time O(V + E), space O(V + E). Every course is expanded once and every arrow followed once; the recursion can be V calls deep.
Same cost. Kahn's writes the order forwards and needs no recursion, so it's the usual first choice. The DFS version is worth knowing because the reverse finishing order idea comes back in harder problems, like finding strongly connected components.
0, 1, ..., n - 1.[], even if most courses could be ordered.