Course Schedule II
Return an order in which every course can be taken — Kahn's algorithm writes it out, and a prerequisite cycle empties it.
Examples
Course 0 has no prerequisites; course 1 needs 0.
LeetCode prints [0,2,1,3]; both respect every pair, and any valid order is accepted.
One course and nothing to wait for.
Problem Understanding
There are numCourses courses labelled 0 to numCourses - 1, and prerequisites[i] = [a, b] means you must take course b before course a.
Return an ordering of the courses in which you could take all of them. If several orders work, return any one; if it is impossible — because some prerequisites form a cycle — return an empty array.
It is Course Schedule with the answer written out: instead of asking whether every course can be taken, return the order you took them in.
Strategy (Kahn's Algorithm)
The Course Schedule method, keeping the order instead of only counting it:
Turn each pair
[course, prereq]into an edgeprereq → course, and count each course's prerequisites.Queue every course with no prerequisites.
Take the front course and append it to the order; each course it unlocks loses one prerequisite, and any that reaches 0 joins the queue.
If the order holds all
numCoursescourses, return it. Otherwise a cycle kept some courses out of the queue for good — return[].
Interactive Visualization
Each arrow runs from a prerequisite to the course it unlocks, and the number above a course is how many of its prerequisites are still untaken. A course joins the order beside the figure the moment it leaves the queue, so the order is the answer being written.
Load Example 2: this run gives [0, 1, 2, 3] where LeetCode prints [0, 2, 1, 3] — 1 and 2 are both freed by 0, and either may go first. Load Cycle to see the order stop short and the answer become [].
Dry Run
LeetCode example 2: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Prerequisite counts start as [0, 1, 1, 2].
| # | Queue | Take | Unlocks | Order |
|---|---|---|---|---|
| 1 | [0] |
0 | 1: 1→0, 2: 1→0 — queue both | [0] |
| 2 | [1, 2] |
1 | 3: 2→1 | [0, 1] |
| 3 | [2] |
2 | 3: 1→0 — queue it | [0, 1, 2] |
| 4 | [3] |
3 | — | [0, 1, 2, 3] |
All 4 courses are in the order: return [0, 1, 2, 3]. LeetCode's [0, 2, 1, 3] is equally valid — any order that respects every pair is accepted.
Solution
Kahn's algorithm in all six languages — the lines light up as the figure above steps.
Course Schedule II Code
1var findOrder = function(numCourses, prerequisites) {2 const graph = Array.from({ length: numCourses }, () => []);3 const indegree = new Array(numCourses).fill(0);4 for (const [course, prereq] of prerequisites) {5 graph[prereq].push(course);6 indegree[course]++;7 }89 const queue = [];10 for (let c = 0; c < numCourses; c++) {11 if (indegree[c] === 0) queue.push(c);12 }13 const order = [];14 let head = 0;15 while (head < queue.length) {16 const course = queue[head++];17 order.push(course);18 for (const unlocked of graph[course]) {19 indegree[unlocked]--;20 if (indegree[unlocked] === 0) queue.push(unlocked);21 }22 }2324 return order.length === numCourses ? order : [];25};
Edge Cases & Common Mistakes
Check for:
Cycle: return an empty array, not
nulland not the partial order — a partial order would silently leave courses out.Many valid orders: any order that respects every pair is accepted; the queue's first-in, first-out rule decides which one this code returns.
Single course, no prerequisites: return
[0].Direction: the pair
[a, b]is the edgeb → a— the prerequisite points at the course it unlocks.