207. Course Schedule

At a Glance

• Topic: Depth-First Search
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 207

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi ...

Approach & Solution Steps

• DFS three-color — gray/black recursion stack — O(V+E).
• Kahn BFS — indegree queue — O(V+E) — either is optimal.

Optimal JS Solution

function canFinish(numCourses, prerequisites) {
  const adjacency = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const edge of prerequisites) {
    const course = edge[0];
    const prerequisite = edge[1];
    adjacency[prerequisite].push(course);
    indegree[course] += 1;
  }
  const queue = [];
  for (let course = 0; course < numCourses; course += 1) {
    if (indegree[course] === 0) {
      queue.push(course);
    }
  }
  let taken = 0;
  while (queue.length > 0) {
    const current = queue.shift();
    taken += 1;
    for (const neighbor of adjacency[current]) {
      indegree[neighbor] -= 1;
      if (indegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }
  return taken === numCourses;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.