64. Course Schedule

MediumGraph DFS BFS

There are numCourses courses, labelled 0 to numCourses - 1. Each entry prerequisites[i] = [a, b] means course b must be completed before course a can be taken.

Return true if there is some order in which every course can be completed, and false otherwise.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true

Explanation: Take course 0, then course 1.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false

Explanation: Each course requires the other first, so neither can ever start.

Example 3

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true

Explanation: One valid order is 0, 1, 2, 3.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a, b < numCourses and a != b
All pairs are distinct

Follow-up: Return an actual order in which to take the courses (or an empty array if none exists).

💡 Hint 1

Model courses as nodes and each prerequisite [a, b] as a directed edge b → a. When is it impossible to finish?

💡 Hint 2

All courses can be finished exactly when the graph has no cycle.

💡 Hint 3

Kahn's algorithm: repeatedly take a course with no remaining prerequisites and remove its outgoing edges. If you manage to take all of them, there is no cycle. (A DFS with three node colours works too.)

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Cycle detection with a topological sort (Kahn's algorithm). Build adjacency lists for edges b → a and count each course's incoming edges (its unmet prerequisites). Start a queue with every course whose count is 0. Each time you take a course from the queue, decrement the count of every course that depends on it and enqueue those that reach 0. If the number of courses taken equals numCourses, the graph is acyclic and everything can be finished. Courses on a cycle never reach 0, so they are never taken.

Time O(V + E)Space O(V + E)

function canFinish(numCourses, prerequisites) {
  const next = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const [course, pre] of prerequisites) {
    next[pre].push(course);
    indegree[course]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indegree[i] === 0) queue.push(i);
  let taken = 0;
  for (let h = 0; h < queue.length; h++) {
    taken++;
    for (const c of next[queue[h]]) {
      if (--indegree[c] === 0) queue.push(c);
    }
  }
  return taken === numCourses;
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) next.add(new ArrayList<>());
        int[] indegree = new int[numCourses];
        for (int[] p : prerequisites) {
            next.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) queue.add(i);
        int taken = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            taken++;
            for (int c : next.get(course)) {
                if (--indegree[c] == 0) queue.add(c);
            }
        }
        return taken == numCourses;
    }
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
function canFinish(numCourses, prerequisites) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit