Course Schedule II
There are numCourses courses labeled 0 to numCourses - 1, with prerequisites given as pairs prerequisitesi = [course, pre]. Return one valid order to take all the courses, or an empty array if it is impossible because the prerequisites form a cycle. Use the same in-degree peeling as Course Schedule, but build the answer array as courses get peeled off instead of just counting them.
Constraints
- 1 ≤ numCourses ≤ 2000
- 0 ≤ prerequisites.length ≤ 5000
- prerequisitesi.length == 2
- All the pairs prerequisitesi are unique
Example
Input
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]Output
[0, 1, 2, 3] (one valid order — others exist too)Explanation Course 0 must go first. Courses 1 and 2 can go in either order after it, then 3 needs both.
In plain terms
- In-degree peeling
- Repeatedly taking any node whose remaining prerequisite count has hit zero, then updating its neighbors' counts.
Build the order by popping in-degree-zero courses one at a time
0—
1—
2—
3—
Statusinit
Queue = [0]. Answer so far: [].
What happens in this step
in-degree[0] = 0, in-degree[1] = 1, in-degree[2] = 1, in-degree[3] = 2 queue = [0] order = [] Only course 0 starts with in-degree 0, so it's the sole entry in the queue before the peeling begins.
Step 1 of 5
Steps to visualize
- Queue every course with an in-degree of zero to start.
- Pop a course from the queue and append it to the answer array.
- Decrement the in-degree of every course it unlocks.
- Any course whose in-degree just hit zero joins the queue.
- If the answer ends up with every course, return it — otherwise return an empty array.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
0—
1—
2—
3—
Statusinit
Queue = [0]. Answer so far: [].
What happens in this step
in-degree[0] = 0, in-degree[1] = 1, in-degree[2] = 1, in-degree[3] = 2 queue = [0] order = [] Only course 0 starts with in-degree 0, so it's the sole entry in the queue before the peeling begins.
Step 1 of 5
Solution
function findOrder(numCourses, prerequisites) {
const inDegree = new Array(numCourses).fill(0);
const graph = Array.from({ length: numCourses }, () => []);
for (const [course, pre] of prerequisites) {
graph[pre].push(course);
inDegree[course]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) {
queue.push(i);
}
}
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const next of graph[node]) {
inDegree[next]--;
if (inDegree[next] === 0) {
queue.push(next);
}
}
}
return order.length === numCourses ? order : [];
}- Time
- O(numCourses + prerequisites.length)
- Space
- O(numCourses + prerequisites.length)
Test cases
| Input | Expected | Covers |
|---|---|---|
numCourses = 3, prerequisites = [[1,0],[2,1]] | [0, 1, 2] | a strict chain where only one order is possible, checked exactly |
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] | contains 0, 1, 2, 3 | branching prerequisites where multiple orders are valid — checked as a set, not one exact sequence |
numCourses = 2, prerequisites = [[1,0],[0,1]] | [] | a cycle makes the course load impossible, so the answer is empty |
numCourses = 3, prerequisites = [] | contains 0, 1, 2 | no constraints at all, so any permutation is valid — checked as a set |
numCourses = 1, prerequisites = [] | [0] | smallest valid input, a single course |
numCourses = 5, prerequisites = [[1,0],[2,1],[3,2],[4,3]] | [0, 1, 2, 3, 4] | a longer strict chain, still only one valid order |
numCourses = 6, prerequisites = [[1,0],[3,2],[5,4]] | contains 0..5 | three independent chains that can interleave many valid ways — checked as a set |
numCourses = 4, prerequisites = [[1,0],[0,1],[3,2]] | [] | a cycle in part of the graph still blocks the whole schedule |