Course Schedule II

1. Define the problem

There are numCourses courses labeled 0 to numCourses - 1, with prerequisites given as pairs prerequisites_i = [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
prerequisites_i.length == 2
All the pairs prerequisites_i are unique

Example

InputnumCourses = 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.

2. Know the words first

In plain terms

In-degree peeling: Repeatedly taking any node whose remaining prerequisite count has hit zero, then updating its neighbors' counts.

3. Visualize the solution

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.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

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

5. Solution

Solution

solution.tsTypeScript

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)

6. Test cases

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

Course Schedule II