medium

Course Schedule

Check whether it is possible to finish every course given their prerequisites.

1. Define the problem

Course Schedule

There are numCourses courses labeled 0 to numCourses - 1. Some courses have prerequisites, given as pairs prerequisitesi = [course, pre] meaning pre must be taken before course. Return true if it is possible to finish every course , or false if the prerequisites form a cycle that makes some course impossible. Build a graph from prerequisite to dependent course, then peel off courses whose in-degree reaches zero — if every course eventually gets peeled, there is no cycle.

Constraints

  • 1 ≤ numCourses ≤ 2000
  • 0 ≤ prerequisites.length ≤ 5000
  • prerequisitesi.length == 2
  • All the pairs prerequisitesi are unique

Example

InputnumCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Outputtrue

Explanation Course 0 first, then 1 and 2 (both need 0), then 3 (needs both 1 and 2) — every course finishes.

2. Know the words first

In plain terms

In-degree
The number of prerequisites a course is still waiting on — edges pointing into it that haven't been resolved yet.
Cycle
A chain of prerequisites that loops back on itself, so some course would need to be taken before itself.
3. Visualize the solution

Peel off courses whose prerequisites are all satisfied

Peel off courses whose prerequisites are all satisfied
Statusinit

in-degree: course0=0, course1=1, course2=1, course3=2. Queue = [0].

What happens in this step

in-degree[0] = 0
in-degree[1] = 1
in-degree[2] = 1
in-degree[3] = 2

queue = [0]

Course 0 is the only course with no unmet prerequisites, so it starts the queue. Courses 1 and 2 each wait on course 0; course 3 waits on both 1 and 2.
Step 1 of 5

Steps to visualize

  1. Build a graph where every prerequisite points to the course that needs it, and count each in-degree.
  2. Queue up every course whose in-degree is already zero.
  3. Pop a course, mark it processed, and decrement the in-degree of every course it unlocks.
  4. Any course whose in-degree just hit zero joins the queue.
  5. If every course got processed, all of them can be finished — otherwise a cycle blocked some.
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.

Peel off courses whose prerequisites are all satisfied
Statusinit

in-degree: course0=0, course1=1, course2=1, course3=2. Queue = [0].

What happens in this step

in-degree[0] = 0
in-degree[1] = 1
in-degree[2] = 1
in-degree[3] = 2

queue = [0]

Course 0 is the only course with no unmet prerequisites, so it starts the queue. Courses 1 and 2 each wait on course 0; course 3 waits on both 1 and 2.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function canFinish(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);
    }
  }

  let processed = 0;

  while (queue.length > 0) {
    const node = queue.shift();
    processed++;
    for (const next of graph[node]) {
      inDegree[next]--;
      if (inDegree[next] === 0) {
        queue.push(next);
      }
    }
  }

  return processed === numCourses;
}
Time
O(numCourses + prerequisites.length)
Space
O(numCourses + prerequisites.length)
6. Test cases

Test cases

InputExpectedCovers
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]truediamond-shaped prerequisites with no cycle
numCourses = 2, prerequisites = [[1,0]]truethe docstring-style smallest non-trivial example
numCourses = 2, prerequisites = [[1,0],[0,1]]falsetwo courses that each require the other
numCourses = 3, prerequisites = []trueno prerequisites at all, nothing blocks any course
numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]truea straight chain of prerequisites
numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]falsea longer three-course cycle
numCourses = 1, prerequisites = []truesmallest valid input, one course and no prerequisites
numCourses = 5, prerequisites = [[1,0],[3,2],[2,3]]falsea cycle hiding inside an otherwise fine, partly disconnected graph

Keep reading